数组范围内计数

数组为 3,2,2,3,1, 查询为(0,3,2)。

意思是在数组里下标 0-3 这个范围上,有几个 2?

假设给一个数组 arr,对这个数组的查询非常频繁请返回所有查询的结果。

给出:arr[ ]

要查多个范围:

[[0,3,2],

[1,4,0]]

结果返回:[第一个数组结果,第二个数组结果]

暴力解法直接遍历肯定不可以。

解法

一、做一个map映射,遍历一遍数组,将每个值和每个值出现的下标位置数组做成key-value

在根据查询的V,在所在值的数组内做二分查找。

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
public static class QueryBox2 {
private HashMap<Integer, ArrayList<Integer>> map;

public QueryBox2(int[] arr) {
map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if (!map.containsKey(arr[i])) {
map.put(arr[i], new ArrayList<>());
}
map.get(arr[i]).add(i);
}
}

public int query(int L, int R, int value) {
if (!map.containsKey(value)) return 0;
ArrayList<Integer> indexArr = map.get(value);
// 查询<L的下标有几个
int a = countLess(indexArr, L);
// 查询<R+1的下标有几个
int b = countLess(indexArr, R + 1);
return b - a;
}

// 在有序数组中,用二分法数出<limit 的数有几个
// 也就是用二分法,找到<limit的数中最右的位置
private int countLess(ArrayList<Integer> arr, int limit) {
int L = 0;
int R = arr.size() - 1;
int mostRight = -1;
while (L <= R) {
int mid = L + ((R - L) >> 1);
if (arr.get(mid) < limit) {
mostRight = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
return mostRight + 1;
}
}

$O(mlogn)$

扩展:

如果是求范围内累加和

可以生成一个前缀和数组类似本题

腾讯原题

给定整数 power。给定一个数组 arr。给定一个数组 reverse。含义如下

arr 的长度一定是 2 的 power 次方,reverse1 每个值一定都在 0 ~ power范围。

例如 power=2, ar={3,1,4,2}, reverse={0,1,0,2}

针对reverse的数组中每一个值

如第一个值为0,就是对$2^0=1$ 每一个arr数组以1个数为单位逆序。

如第二个值为1,就是对$2^1=2$ 对arr数组每两个数逆序

任何一个在前的数字可以和任何一个在后的数组,构成一对数。可能是升序关系、相等关系或者降序关系。

最后求调整完的arr数组有多少个降序对。

比如 arr 开始时有如下的降序对:(3,1)、(3.2)、(4.2),一共 3 个。

以2个数调整后arr由{3,1,4,2} 变成{1,3,2,4} 降序对有{3,2} ,共1个

经典做法每次都reverse

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
// originArr长度一定是2的power次方
// reverseArr中每一个值,都是0-power范围上的数
public static int[] reversePair1(int[] originArr, int[] reverseArr, int power) {
int[] ans = new int[reverseArr.length];
for (int i = 0; i < reverseArr.length; i++) {
// 1 << (reverseArr[i]) == r[i]的2次方
reverseArray(originArr, 1 << (reverseArr[i]));
ans[i] = countReversePair(originArr);
}
return ans;
}

public static void reverseArray(int[] originArr, int teamSize) {
if (teamSize < 2) return;
for (int i = 0; i < originArr.length; i += teamSize) {
reversePart(originArr, i, i + teamSize - 1);
}
}

public static void reversePart(int[] arr, int L, int R) {
while (L < R) {
int temp = arr[L];
arr[L++] = arr[R];
arr[R--] = temp;
}
}

public static int countReversePair(int[] originArr) {
int ans = 0;
for (int i = 0; i < originArr.length; i++) {
for (int j = i + 1; j < originArr.length; j++) {
if (originArr[i] > originArr[j]) {
ans++;
}
}
}
return ans;
}

优化方案

[3,2 4,5, 0,1 3,5]

两个数一组: 1个逆序对,3个升序对

四个数一组: 0个逆序对,8个升序对

八个数一组:10个逆序对,4个升序对

每个数组的逆序对数是2、4、9个一组的加和

当数组进行几个数一组翻转时

翻转后的逆序对和升序对数量,和翻转前的升序对和逆序对相等,数量调换了。

小的数调整后数量不影响大数量调整后的数量。

所以直接查2、4、8、16个 数量再交换相加。

如何高效生成预处理记录

输入数据状况

power范围[0,20]

arr长度范围[1,10e7]

reverse长度范围[1,10e6]

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
public static int[] reversePair2(int[] originArr, int[] reverseArr, int power) {
int[] originReverse = Arrays.copyOf(originArr, originArr.length);
reversePart(originReverse, 0, originReverse.length - 1);
int[] recordDown = new int[power + 1];
int[] recordUp = new int[power + 1];
process(originArr, 0, originArr.length - 1, power, recordDown);
process(originReverse, 0, originReverse.length - 1, power, recordUp);

// recordDown[i] 2的i次方个数一组的划分中,降序的数量
// recordUp[i] 2的i次方个数一组的划分中,升序的数量
int[] ans = new int[reverseArr.length];
for (int i = 0; i < reverseArr.length; i++) {
int curPower = reverseArr[i]; // =3 2的1次方、2次方、3次方 要调整
for (int p = 1; p <= curPower; p++) {
int tmp = recordDown[p];
recordDown[p] = recordUp[p];
recordUp[p] = tmp;
}
for (int p = 1; p <= power; p++) {
ans[i] += recordDown[p];
}
}
return ans;
}

public static void process(int[] originArr, int L, int R, int power, int[] record) {
if (L == R) {
return;
}
int mid = L + ((R - L) >> 1);
process(originArr, L, mid, power - 1, record);
process(originArr, mid + 1, R, power - 1, record);
record[power] += merge(originArr, L, mid, R);
}

public static int merge(int[] arr, int L, int m, int r) {
int[] help = new int[r - L + 1];
int i = 0;
int p1 = L;
int p2 = m + 1;
int ans = 0;
while (p1 <= m && p2 <= r) {
ans += arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
return ans;
}