Leetcode: 面试题51. 数组中的逆序对分治归并

124 阅读 0 评论 82 点赞

我是靠谱客的博主甜甜黄蜂，这篇文章主要介绍Leetcode: 面试题51. 数组中的逆序对分治归并，现在分享给大家，希望可以做个参考。

题目

题目链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

复制代码

1
2
3
4
5
6
示例 1:

输入: [7,5,6,4]
输出: 5

限制：

复制代码

1
2
0 <= 数组长度 <= 50000

解题记录

通过分治的思路，使用归并排序的逻辑
通过递归合并
在归并的基础上添加计数功能 count += (mid+1-idx1)

复制代码

class Solution {
    public int reversePairs(int[] nums){
        int len = nums.length;
        if (len<2) return 0;
        int[] tmp = new int[len];
        return split(nums, 0, len-1, tmp);
    }

private int split(int[] nums, int start, int end, int[] tmp) {
        if(start==end) return 0;
        int mid = (start+end)>>1;
        int leftCount = split(nums, start, mid, tmp);
        int rightCount = split(nums, mid+1, end, tmp);
        if(nums[mid] <= nums[mid+1]) return leftCount+rightCount;
        int mixCount = merge(nums, start, mid, end, tmp);
        return leftCount+mixCount+rightCount;
    }

private int merge(int[] nums, int start, int mid, int end, int[] tmp) {
        if (end + 1 - start >= 0) System.arraycopy(nums, start, tmp, start, end + 1 - start);
        int idx1 = start, idx2 = mid+1;
        int count=0;
        for (int i=start; i<=end; ++i){
            if( idx1 > mid ){
                nums[i] = tmp[idx2];
                ++idx2;
            } else if (idx2 > end) {
                nums[i] = tmp[idx1];
                ++idx1;
            } else if (tmp[idx1] <= tmp[idx2]) {
                nums[i] = tmp[idx1];
                ++idx1;
            } else {
                nums[i] = tmp[idx2];
                ++idx2;
                count += (mid+1-idx1);
            }
        }
        return count;
    }
}

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
class Solution {
    public int reversePairs(int[] nums){
        int len = nums.length;
        if (len<2) return 0;
        int[] tmp = new int[len];
        return split(nums, 0, len-1, tmp);
    }

    private int split(int[] nums, int start, int end, int[] tmp) {
        if(start==end) return 0;
        int mid = (start+end)>>1;
        int leftCount = split(nums, start, mid, tmp);
        int rightCount = split(nums, mid+1, end, tmp);
        if(nums[mid] <= nums[mid+1]) return leftCount+rightCount;
        int mixCount = merge(nums, start, mid, end, tmp);
        return leftCount+mixCount+rightCount;
    }

    private int merge(int[] nums, int start, int mid, int end, int[] tmp) {
        if (end + 1 - start >= 0) System.arraycopy(nums, start, tmp, start, end + 1 - start);
        int idx1 = start, idx2 = mid+1;
        int count=0;
        for (int i=start; i<=end; ++i){
            if( idx1 > mid ){
                nums[i] = tmp[idx2];
                ++idx2;
            } else if (idx2 > end) {
                nums[i] = tmp[idx1];
                ++idx1;
            } else if (tmp[idx1] <= tmp[idx2]) {
                nums[i] = tmp[idx1];
                ++idx1;
            } else {
                nums[i] = tmp[idx2];
                ++idx2;
                count += (mid+1-idx1);
            }
        }
        return count;
    }
}