算法——序列

引言

本文整理了常见的序列相关算法,方便以后查阅。算法相关的文章均收录于<算法系列文章>

最大子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package bbm.sequence;

/**
* 基于分治思想的最大子序列,递归地将序列分割成两半,然后比较左半段,右半段,和中间跨越的段,最终取最大的作为结果
*
* 时间复杂度: O(n*log(n))
* 空间复杂度: O(log(n)) 栈
*
* @author bbm
*/
public class MaxSubSequence {
public int maxSubArray(int[] nums) {
if (nums == null) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
return findMaxArray(nums, 0, nums.length - 1);
}

private int findMaxArray(int[] nums, int low, int max) {
if (low == max) {
return nums[low];
}
int mid = (low + max) / 2;
int leftMax = findMaxArray(nums, low, mid);
int rightMax = findMaxArray(nums, mid + 1, max);
int midMax = findCrossArray(nums, low, mid, max);
return Math.max(Math.max(leftMax, rightMax), midMax);
}

private int findCrossArray(int[] nums, int low, int mid, int max) {
int leftMax = Integer.MIN_VALUE;
int sum = 0;
for (int x = mid; x >= low; x--) {
sum += nums[x];
if (sum > leftMax) {
leftMax = sum;
}
}
sum = 0;
int rightMax = Integer.MIN_VALUE;
for (int x = mid + 1; x <= max; x++) {
sum += nums[x];
if (sum > rightMax) {
rightMax = sum;
}
}
return leftMax + rightMax;
}
}

测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package bbm.sequence;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
* @author bbm
*/
public class MaxSubSequenceTest {
@Test
public void testMaxSubSeq() {
MaxSubSequence maxSubSequence = new MaxSubSequence();
int result = maxSubSequence.maxSubArray(new int[] {-2, -1, 1 ,1, 4, -3, -4, 3});
Assertions.assertEquals(6, result);
}
}

顺序统计量

随机顺序统计量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package bbm.order;

import java.util.HashSet;
import java.util.Set;

/**
* 顺序统计量,即获取某一数组中第 N 大的数(n=3),这并不需要对整个数组进行排序,本例中采用了随机快速排序的思想
* 但是只会对分割出来的两部分中的一个进行递归处理
*
* 平均时间复杂度: O(n)
* 最差时间复杂度: O(n ^ 2)
*
* @author bbm
*/
public class RandomOrderStatistic implements OrderStatistic{

private static final int n = 3;

@Override
public int getNLargestNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
nums = new int[set.size()];
int index = 0;
for (int num : set) {
nums[index++] = num;
}
int smallestN;
if (nums.length - n + 1 > 0) {
smallestN = nums.length - n + 1;
} else {
smallestN = nums.length;
}
return select(nums, 0, nums.length - 1, smallestN);
}

private int select(int[] nums, int p, int q, int n) {
if (p == q) {
return nums[p];
}
int r = partition(nums, p, q);
int k = r - p + 1;
if (n == k) {
return nums[r];
}
if (n < k) {
return select(nums, p, r - 1, n);
} else {
return select(nums, r + 1, q, n - k);
}
}

private static int partition(int[] nums, int p, int r) {
int pivot = nums[r];
int leftEnd = p - 1;
for (int rightEnd = p; rightEnd < r; rightEnd++) {
if (nums[rightEnd] < pivot) {
leftEnd++;
int temp = nums[leftEnd];
nums[leftEnd] = nums[rightEnd];
nums[rightEnd] = temp;
}
}
leftEnd++;
int temp = nums[leftEnd];
nums[leftEnd] = nums[r];
nums[r] = temp;
return leftEnd;
}
}

稳定顺序统计量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package bbm.order;

import java.util.HashSet;
import java.util.Set;

/**
* 在 {@link RandomOrderStatistic} 中最差时间复杂度到了 O(n^2) 这是快排中也会出现的问题,即便进行了随机化,也是可能出现该问题,
* 所以在本例中,我们不再选用最后一个数作为主元素,而是我们指定一个特定的元素,该元素需要保持划分的平衡性,这样才能保证时间复杂度收敛与 O(n)
*
* 具体的做法是:
* 将n个元素划分为n/5组
* 寻找每组的中位数
* 找出的中位数的中位数x, 这个中位数的性质是 有 1/4 的数小于它并且有 1/4 的数大于它,所以选用它来做主元素比较平衡
* 使用x作为主元素执行快排的 PARTITION,计算得出 x 为第 k 小的元素
* 如果目标值 i==k,返回x;如果i<k,在低区调用PARTITION找出第i小的元素;如果i>k,在高区调用PARTITION查找第i-k小的元素
*
* 时间复杂度: O(n)
*
* @author bbm
*/
public class StableOrderStatistic implements OrderStatistic{

private static final int n = 3;

@Override
public int getNLargestNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
nums = new int[set.size()];
int index = 0;
for (int num : set) {
nums[index++] = num;
}
int smallestN;
if (nums.length - n + 1 > 0) {
smallestN = nums.length - n + 1;
} else {
smallestN = nums.length;
}
return select(nums, 0, nums.length - 1, smallestN, findMidNumber(nums));
}

private int select(int[] nums, int start, int end, int smallestN, int pivotIndex) {
if (start == end) {
return nums[start];
}
int rightIndex = partition(nums, start, end, pivotIndex);
int order = rightIndex - start + 1;
if (smallestN == order) {
return nums[rightIndex];
}
if (smallestN < order) {
return select(nums, start, rightIndex - 1, smallestN, rightIndex - 1);
} else {
return select(nums, rightIndex + 1, end, smallestN - order, rightIndex + 1);
}
}

private int findMidNumber(int[] nums) {
int size = (int) Math.ceil((double) nums.length / 5);
int[][] groupedNums = new int[size][5];
int[] indexes = new int[size];
for (int i = 0; i < nums.length; i++) {
int slot = i % groupedNums.length;
groupedNums[slot][indexes[slot]] = nums[i];
int tmp = indexes[slot];
for (int j = indexes[slot] - 1; j >= 0; j--) {
if (tmp < groupedNums[slot][j]) {
groupedNums[slot][j + 1] = groupedNums[slot][j];
groupedNums[slot][j] = tmp;
}
}
indexes[slot] += 1;
}
int[] midNumbers = new int[size];
int index = 0;
for (int i = 0; i < groupedNums.length; i++) {
if (indexes[i] == 5) {
midNumbers[index++] = groupedNums[i][3];
} else {
midNumbers[index++] = groupedNums[i][indexes[i] / 2];
}
}
int finalMid = select(midNumbers, 0, midNumbers.length - 1, size / 2, 0);
int finalMidIndex = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == finalMid) {
finalMidIndex = i;
}
}
return finalMidIndex;
}

private static int partition(int[] nums, int p, int r, int position) {
int temp = nums[position];
nums[position] = nums[r];
nums[r] = temp;
int pivot = nums[r];
int leftEnd = p - 1;
for (int rightEnd = p; rightEnd < r; rightEnd++) {
if (nums[rightEnd] < pivot) {
leftEnd++;
temp = nums[leftEnd];
nums[leftEnd] = nums[rightEnd];
nums[rightEnd] = temp;
}
}
leftEnd++;
temp = nums[leftEnd];
nums[leftEnd] = nums[r];
nums[r] = temp;
return leftEnd;
}
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package bbm.order;

import com.google.common.primitives.Ints;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.stream.Collectors;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
* @author bbm
*/
class RandomOrderStatisticTest {
@Test
public void testGetNSmallestNumber() {
doTest(new RandomOrderStatistic());
doTest(new StableOrderStatistic());
}

private void doTest(OrderStatistic orderStatistic) {
int dataSize = 10000;
int[] data = new int[dataSize];
Random rand = new Random(System.currentTimeMillis());
for (int i = 0; i < dataSize; i++) {
data[i] = rand.nextInt(dataSize);
}
Arrays.sort(data);
Collections.reverse(Ints.asList(data));
int rightResult = Ints.asList(data).stream().distinct().collect(Collectors.toList()).get(2);
int result = orderStatistic.getNLargestNumber(data);
Assertions.assertEquals(rightResult, result);
}
}

参考内容

[1] 《算法导论》

贝克街的流浪猫 wechat
您的打赏将鼓励我继续分享!
  • 本文作者: 贝克街的流浪猫
  • 本文链接: https://www.beikejiedeliulangmao.top/algorithm/sequence/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
  • 创作声明: 本文基于上述所有参考内容进行创作,其中可能涉及复制、修改或者转换,图片均来自网络,如有侵权请联系我,我会第一时间进行删除。