数组逆序对个数问题【2】
2022-10-26 07:54:36 # 算法 # 排序 #归并排序

1. 问题描述

给定一个数组array，和一个正整数p，数组的长度len是$2^p$，再给定一个数组reverseGroup，他的数组元素的范围是$[0,p]$。我们需要返回一个答案数组ans，ans[i]表示把原数组按照$2^{reverseGroup[i]}$个元素为一组反转后，数组中逆序对的个数。

p的范围$[1,10]$，reverseGroup[i]的范围$[1,100]$。

例如：

array=[1,2,3,4,5,6,7,8], reverseGroup = [0,1,2], p = 3;

  1. 首先把原数组按照$2^0 = 1$个元素一组反转，此时相当于没有反转，逆序对个数0，因此ans[0] = 0;
  2. 然后把数组按照$2^1 = 2$个元素为一组进行反转，反转后的数组array=[2,1,4,3,6,5,8,7]，逆序对个数是4，ans[1] =4，
  3. 然后把数组按照$2^2 = 4$个元素为一组进行反转，反转后的数组array=[3,4,1,2,7,8,5,6]，逆序对的个数是4，ans[2] = 4,

于是返回ans=[0,4,4]；

2. 暴力解法

直接模拟即可，代码如下：

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
public class ReversePairCount2 {
    
    public static int[] count(int[] array, int[] reverseGroup, int p) {
        int rLen = reverseGroup.length, pre = -1;
        int[] ans = new int[rLen];
        for(int i = 0; i < rLen; ++i) {
            if(reverseGroup[i] == 0) {
                if(pre == -1) pre = getReversePairCount(array);
            }else {
                reverseByGroup(array, 1 << reverseGroup[i]);
                pre = getReversePairCount(array);
            }
            ans[i] = pre;
        }
        return ans;
    }
    
    private static int getReversePairCount(int[] array) {
        int len = array.length, ans = 0;
        for(int i = 0; i < len; ++i) {
            for(int j = i + 1; j < len; ++j) {
                if(array[i] > array[j]) ++ans;
            }
        }
        return ans;
    }
    
    private static void reverseByGroup(int[] array, int group) {// group个元素为一组，反转数组。
        int i = 0, len = array.length, j;
        while(i < len) {
            j = i + group - 1;
            reverseRange(array, i, j);
            i = j + 1;
        }
    }
    
    private static void reverseRange(int[] array, int i, int j) {// 反转一块数组
        while(i < j) {
            int t = array[i];
            array[i++] = array[j];
            array[j--] = t;
        }
    }
}

时间复杂度$O(N^2*rLen)$，空间复杂度$O(1)$。

3. 最优解

3.1. 算法分析

使用归并排序的merge过程，先按照两个数为一组求解所有组中的逆序对；然后按照4个数为一组求解所有组的逆序对（求解4个数为一组的逆序对的时候，需要把一组的4个数，分成左右两组，左右两组每组两个数，只考虑左右两组之间能产生多逆序对，而不要考虑左组内部有多少逆序对，右组内部有多少逆序对，这是因为左右两组内部的逆序对在上一步的时候已经求解过了），然后按照8个数为一组求解所有组的逆序对（同样，求解8个数为一组的时候，每一组分成左右两组，左右两组每组4个数，我们只需要求解左右两组之间可以产生多少逆序对），…，一直求解到按照$2^p$个数为一组的时候，逆序对的个数。

我们把每一步的答案都记录下来，根据数组长度是$2^p$，我们一共可以得到p个答案，因此数组中总的逆序对的个数就是这p个答案的加和。

为什么要这么做呢？

这是因为当反转的时候，我们没有必要去真的反转数组，只需要调整我们上面求得的答案，就可以快速获取反转后的答案。当我们要求4个数为一组反转后的答案的时候，可以知道4个数为一组反转后，它不影响我们上面求解的8个数为一组的时候的答案（因0为8个数为一组的答案是左右两组之间形成的逆序对的个数，左右组反转了（实际上左右组内的数据无论被洗牌成什么样，只会影响左右组自己组内的逆序对的个数，而不会影响左右两组之间形成的逆序对的个数），那么反转会使得4个数为一组，2个数为一组的逆序对的个数发生变化，变成了什么呢？其实反转以后，他们的逆序对的个数，就是反转之前正序对的个数，因此我们只需要求得2个数为一组，4个数为一组，…，$2^p$个数为一组的正序对，逆序对的个数就可以了。这样当发生反转的时候，例如$2^i$个数为一组进行反转，我们只需要从$2^1,2^2,…,2^i$，这些组的逆序对个数和正序对个数交换，那么就可以修正原来逆序对的答案数组，每一步的答案就是修正后的逆序对的答案数组的元素加和。

于是我们有如下算法：

设置两个答案数组reverseCountByGroup和normalCountByGroup，分别代表数组各个分组的逆序对个数和正序对个数。然后使用归并排序的方法，对数组求解逆序对和正序对的个数，把答案写在数组中。

设置答案数组ans，然后遍历reverseGroup数组，对每一个反转分组rGroup，进行如下步骤：

  1. 如果rGroup>0，那么对所有的i从0到rGroup-1，把reverseCountByGroup[i] 和 normalCountByGroup[i]，互换。
  2. i从0到p-1，把reverseCountByGroup[i]累加起来，作为当前这次的答案放入ans中。

例如，array=[1,3,5,7,2,4,6,8], reverseGroup=[1,2,0,3],

array长度len = 8; p = 3。

因此reverseCountByGroup和normalCountByGroup的长度是3

  1. reverseCountByGroup[0]的值是按照两个数为一组的时候，逆序对的总个数，因为两个数一组的时候，没有逆序对，因此reverseCountByGroup[0]=0;
  2. reverseCountByGroup[1]的值是按照4个数为一组的时候，因此第一组[1,3,5,7]，分成左右两组[1,3],[5,7]，这两组之间没有逆序对，同样[2,4,6,8]也没有逆序对。因此reverseCountByGroup[1]=0;
  3. reverseCountByGroup[2]的值是按照8个数为一组的时候，第一祖[1,3,5,7,2,4,6,8]，分成左右两组，左组[1,3,5,7]，右组：[2,4,6,8]，这两组之间可以产生逆序对（3,2），（5,2），（5,4），（7,2），（7,4），（7,6）。因此一共有6个，因此reverseCountByGroup[2]=6;

求解normalCountByGroup是类似的方法。因此

normalCountByGroup=[4,4,10]

reverseCountByGroup=[0,0,6]

reverseGroup[0] = 1, 即两个数一组进行反转，因此我们需要把normalCountByGroup[0]和reverseCountByGroup[0]进行互换，因此normalCountByGroup=[0,4,10]，reverseCountByGroup=[4,0,6]，于是反转后，逆序对的总个数是4+0+6=10

reverseGroup[1] = 2, 即4个数一组进行反转，因此我们需要把normalCountByGroup[0…1]和reverseCountByGroup[0…1]进行互换，因此normalCountByGroup=[4,0,10]，reverseCountByGroup=[0,4,6]，于是反转后，逆序对的总个数是0+4+6=10

…

剩下的也是类似的做法。

3.2. 代码

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
public class ReversePairCount22 {
    
    public static int[] count(int[] array, int[] reverseGroup, int p) {
        int[] reverseAns = new int[p], 
        	normalAns = new int[p], 
        	arrayCopy = new int[array.length], 
        	h = new int[array.length], 
        	ans = new int[reverseGroup.length];
        for(int i = 0; i < array.length; ++i) arrayCopy[array.length - 1 - i] = array[i];
        getReversePairCntAns(array, reverseAns, h);
        getReversePairCntAns(arrayCopy, normalAns, h);
        int pre = -1;// 因为当reverseGroup[i]==0的时候，此时的答案可以采用上一步的答案，因此pre代表上一步的答案。当pre==-1的时候，代表上一步的答案无效。
        for(int i = 0; i < reverseGroup.length; ++i) {
            if(reverseGroup[i] > 0) {
                for(int j = 0; j < reverseGroup[i]; ++j) {// 如果翻转了，那么就需要下标从范围[0,reverseGroup[i] - 1]，reverseAns 和 normalAns 互换，这是因为反转了以后，正序对的个数就变成逆序对的个数。 
                    int t = reverseAns[j];
                    reverseAns[j] = normalAns[j];
                    normalAns[j] = t;
                }
                pre = -1;// 此时发生了反转，令上一步答案失效
            }
            if(pre == -1) {// 如果上一步答案失效，那么需要重新计算答案。
                pre = 0;
                for(int j = 0; j < p; ++j) pre += reverseAns[j];
            }
            ans[i] = pre;
        }
        return ans;
    }
    
    private static void getReversePairCntAns(int[] array, int[] ans, int[] h) {
        int l, m, r, i = 0, g = 1, len = array.length, t;
        while(g < len) {
            l = 0;
            t = 0;
            while(l < len - 1) {
                if((m = l + g - 1) >= len - 1) break;
                r = Math.min(len - 1, m + g);
                t += merge(array, l, m, r, h);
                l = r + 1;
            }
            ans[i++] = t;
            if(g > (len >> 1)) break;
            g <<= 1;
        }
    }
    
    private static int merge(int[] array, int l, int m, int r, int[] h) {
        int i = l, j = m + 1, k = 0, ans = 0;
        while(i <= m) {
            while(j <= r && array[i] > array[j]) ++j;
            ans += j - m - 1;
            ++i;
        }
        i = l;
        j = m + 1;
        while(i <= m && j <= r) h[k++] = array[i] <= array[j] ? array[i++] : array[j++];
        while(i <= m) h[k++] = array[i++];
        while(j <= r) h[k++] = array[j++];
        System.arraycopy(h, 0, array, l, k);
        return ans;
    }
}

数组array长度N，reverseGroup数组长度是R，那么时间复杂度$O(max{p*R,N\log_2N})$，空间复杂度$O(N)$。

4. 测试程序

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
import java.util.*;

public class ReversePairCount2Test {
    
    public static void main(String[] args) {
        int time = 100_0000, maxP = 6, maxReverseGroupSize = 10;
        while(time-- > 0) {
            Random r = new Random();
            int p = r.nextInt(maxP) + 1, size = 1 << p, groupSize = r.nextInt(maxReverseGroupSize) + 1;
            int[] array1 = new int[size], array2 = new int[size], array3 = new int[size],
            	group1 = new int[groupSize], group2 = new int[groupSize], group3 = new int[groupSize];
            for(int i = 0; i < size; ++i) array1[i] = array2[i] = array3[i] = r.nextInt(201) - 100;
            for(int i = 0; i < groupSize; ++i) group1[i] = group2[i] = group3[i] = r.nextInt(p + 1);
            int[] ans1 = ReversePairCount2.count(array1, group1, p), ans2 = ReversePairCount22.count(array2, group2, p);
            for(int i = 0; i < groupSize; ++i) {
                if(ans1[i] != ans2[i]) {
                    System.out.println("Oops! answer incorrect!!, ans1[" + i + "] = " + ans1[i] + ", ans2[" + i + "] = " + ans2[i]);
                    System.out.println(Arrays.toString(ans1));
                    System.out.println(Arrays.toString(ans2));
                    System.out.println(Arrays.toString(array3));
                    System.out.println(Arrays.toString(group3));
                    System.out.println(p);
                    System.out.println(groupSize);
                    return;
                }
            }
            System.out.println("Testcase: " + time + " done!");
        }
        System.out.println("Test done successfully !!");
    }
}
上一页
2022-10-26 07:54:36 # 算法 # 排序 #归并排序
下一页