493. Reverse Pairs 

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
class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    private int mergeSort(int[] nums, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return 0;
        }

        // [startIndex, midIndex], [midIndex + 1, endIndex]
        int midIndex = (startIndex + endIndex) >>> 1;
        int leftCount = mergeSort(nums, startIndex, midIndex);
        int rightCount = mergeSort(nums, midIndex + 1, endIndex);

        // 左侧数组与右侧数组已经有序，注意仅处理 [startIndex, endIndex] 这部分元素
        int reversePairs = leftCount + rightCount;
        
        // 低效的实现，会超时
//        for (int i = startIndex; i <= midIndex; i++) {
//            for (int j = midIndex + 1; j <= endIndex; j++) {
//                if ((long) nums[i] > (long) 2 * nums[j]) {
//                    reversePairs++;
//                } else {
//                    break;
//                }
//            }
//        }

        // 关键之处在于将 j 变量声明在循环之外，能够降低时间复杂度，因为复用了之前的比较结果
        int i = startIndex, j = midIndex + 1; 
        while (i <= midIndex) {
            while (j <= endIndex && nums[i] > (long) 2 * nums[j]) {
                j++;
            }
            // now: j does not meet the conditions
            reversePairs += j - midIndex - 1;
            i++;
        }

        int[] tmp = new int[endIndex - startIndex + 1];

        i = startIndex;
        j = midIndex + 1;
        for (int k = startIndex; k <= endIndex; k++) {
            if (i == midIndex + 1) {
                tmp[k - startIndex] = nums[j++];
            } else if (j > endIndex) {
                tmp[k - startIndex] = nums[i++];
            } else if (nums[i] <= nums[j]) {
                tmp[k - startIndex] = nums[i++];
            } else {
                tmp[k - startIndex] = nums[j++];
            }
        }

        for (int k = startIndex; k <= endIndex; k++) {
            nums[k] = tmp[k - startIndex];
        }

        return reversePairs;
    }    
}

关键点在于中间的比较逻辑。

References

493. Reverse Pairs