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

题目

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

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

示例 1:

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

限制：

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;
    }
}

最后

以上就是甜甜黄蜂为你收集整理的Leetcode: 面试题51. 数组中的逆序对 分治归并的全部内容，希望文章能够帮你解决Leetcode: 面试题51. 数组中的逆序对 分治归并所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。