【数据结构】算法 计算数组中的逆序对

目录

• 数组中的逆序对
  • 思路
• Tag

数组中的逆序对

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

思路

这个问题最好想的是暴力破解，就是循环循环。来判断构成逆序的数。但是这个会带来的问题，就是超时。毕竟时间复杂度是O(n^2)

另一个方法是通过归并排序。

归并排序的特征就是先拆分，后合并。把原始数组拆分成m个数组，再对这m个小数组排序，此时形成了m个有序数组。然后在合并的过程中计算逆序对。因为在拆分的过程中数组中m个数，最终会被拆成m个一个元素的数组，此时合并的时候，就可以避免重复的计算。

能理解上面的内容，接下来要思考的就是具体点的东西了，逆序对计算。

归并的合并部分，我们需要计算的是3个部分的逆序对。

• 左边区间的逆序对。
• 右边区间的逆序对。
• 跨区间的逆序对。

class Solution {
    private int[] tmp;
    public int reversePairs(int[] nums) {
        tmp =new int[nums.length];
        return count(nums,0,nums.length-1);
        
    }

    public int count(int[] nums ,int l ,int r){
        if(l>=r){
            return 0;
        }
        int mid = (l+r)>>1;
        int ans =0;
        ans += count(nums,l,mid);
        ans += count(nums,mid+1,r);
        int k = l, p1 =l, p2 = mid+1;

        while(p1<=mid||p2<=r){
            if((p2>r)||(p1<=mid&&nums[p1]<=nums[p2])){
                tmp[k++] = nums[p1++];
            }
            else{
                tmp[k++] = nums[p2++];
                ans += (mid -p1 +1);//from p1 to mid ,there (mid-p1+1) nums bigger than nums[p2]
            }
        }
        for (int i = l; i <=r ; i++) {
            nums[i] = tmp[i];
        }
        return ans;
    }
}

排序的操作是必须的，不排序，后面的归并计算就会不正常

Tag

归并