【算法】Reverse Pairs 翻转对，merge sort

题目

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2
Example2:

Input: [2,4,3,5,1]
Output: 3
Note:
The length of the given array will not exceed 50,000.
All the numbers in the input array are in the range of 32-bit integer.

给出一整数数组nums，找出符合 i<j ，同时 nums[i] > 2*nums[j]的数对个数：

1. 数组长度不会超过 50000
2. 所有整数都在 32 位整数范围内

解题思路

本题的条件有两个：

1. i < j
2. nums[i] > num[j] * 2

可以用分治法，将一个大问题化成若干个小问题：

1. mergesort_and_count 中将 nums 从 mid 划分为两段数组，进行并归调用 mergesort_and_count 计算结果
2. mergesort_and_count 中逐一比对 mid 左右两段的数字，找到符合 nums[i] > num[j] * 2 的数对，加值 count 后返回
   1. 分治时，若是暴力比对，则需要将 mid 右侧的所有数字都进行比对
   2. 若是在比对前左右就是有序数组的话，就可以比较到不符数对后即可返回，节省了比对的时间
   3. 所以这里就可以引出分治排序法中的并归排序（merge sort）了，在进行分治时，同时进行排序和比对操作
   4. 在分支到最深处，其实就是两个元素的数组，比对完之后，用 merge sort 进行排序，这样在下次比对时，mid 左右两侧就是有序数组了

代码实现

Runtime: 968 ms
Memory Usage: 21.6 MB

    func reversePairs(_ nums: [Int]) -> Int {
        //转化为可变数组
        var numArr = nums
        //通过 mergesort_and_count 进行排序和计算结果
        return self.mergesort_and_count(&numArr, start: 0, end: nums.count - 1);
    }
    //计算 nums 中 start ... end 范围内的元素中符合 i<j && nums[i] > nums[j] * 2 的数对个数
    //同时进行 mergesort 排序
    func mergesort_and_count(_ nums: inout [Int], start: Int, end: Int)->Int{
        //如果 start < end 才进行操作，否则返回符合条件数对个数为 0
        if (start < end) {
            //从中拆分 nums ，递归
            let mid = (start + end) / 2;
            var j = mid + 1;
            // count 记录符合条件数对个数
            var count = self.mergesort_and_count(&nums, start: start, end: mid) + self.mergesort_and_count(&nums, start: j, end: end);
            //遍历寻找 start <= i <= mid < j <= end 中，nums[i] > nums[j] * 2 的数对个数，并加到 count
            //由于 mid 左右两边都进行了升序排序，所以 j 找到第一个不符合 nums[i] > nums[j] * 2 后即可退出 while 循环，因为在后面都是更大的数，一定会不符合
            for i in start ... mid {
                while (j <= end && nums[i] > nums[j] * 2) {
                    j += 1
                }
                count += j - (mid + 1);
            }
            //mergesort排序
            self.merge(&nums, start: start, mid: mid, end: end);
            //返回结果
            return count;
        }else{return 0;}
    }
    func merge(_ nums: inout [Int], start: Int, mid: Int, end: Int)->Void
    {
        //将数组从 mid 拆分成两个子数组，逐一比对，返回较小者
        let n1 = (mid - start + 1);
        let n2 = (end - mid);
        var L = [Int]();
        var R = [Int]();
        for i in 0 ..< n1{
            L.append(nums[start + i])
        }
        for j in 0 ..< n2{
            R.append(nums[mid + 1 + j])
        }
        var i = 0
        var j = 0
        for k in start ... end {
            if (j >= n2 || (i < n1 && L[i] <= R[j])){
                nums[k] = L[i];
                i+=1
            }else{
                nums[k] = R[j];
                j+=1
            }
        }
    }

代码地址：https://github.com/sinianshou/EGSwiftLearning