剑指 Offer 51. 数组中的逆序对-Toy模板网

这篇具有很好参考价值的文章主要介绍了剑指 Offer 51. 数组中的逆序对。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

剑指 Offer 51. 数组中的逆序对

【归并】朴实无华的一个归并排序的应用，对于一个数组，我们通过归并排序来从大到小进行排序，在合并的过程中如果前面区间有比后面区间大的元素，那么后面区间从这个元素开始一直到结束都能和前面区间的那个数组成逆序对。

举个🌰：

7，5，6，4，3

我们知道归并排序是先划分然后再合并，最底层的肯定就是单个元素，所以一开始的时候：（啊不对，还是算一算区间划分吧，第一层[0, 2] [3, 4], 第二层[0, 1] [2] [3] [4], 第一个划分第三层）

第三层：[7], [5]

归并的时候我们发现7 > 5，说明组成了一个逆序对。合并后是[7, 5]；

第二层：先合并[7, 5], [6] 再合并 [4], [3]；

7 > 6，增加一个逆序对；合并为[7, 6, 5]；

4 > 3，增加一个逆序对；合并为[4, 3]。

第一层合并[7, 6, 5]和[4, 3]

7 > 4，增加两个逆序对，注意这里是两个，因为4后面肯定比4还小，另外此时7已经归并到最终数组去了；

6 > 4，再增加两个逆序对；

5 > 4，再增加两个逆序对。

所以总结下来，这个的精髓就是在归并A，B区间的过程中，如果发现A区间的元素a>B区间的元素b，那么B区间从b开始剩下的元素肯定能和a组成逆序对（在归并过程中a和b都是现存的区间的最顶元素了）。文章来源地址https://www.toymoban.com/news/detail-430406.html

class Solution {

    // 归并 4:38 5

    int ans = 0, n;
    int[] nums, tmp; 

    void mergeSort(int l, int r){
        if(l >= r) return;
        int mid = (l + r) >>> 1;
        mergeSort(l, mid); mergeSort(mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        while(i <= mid && j <= r){
            if(nums[i] > nums[j]){
                ans += (r - j + 1);
                tmp[k++] = nums[i++];
            }else{
                tmp[k++] = nums[j++];
            }
        }
        while(i <= mid) tmp[k++] = nums[i++];
        while(j <= r) tmp[k++] = nums[j++];
        for(i = l, j = 0; j < k; i++, j++) nums[i] = tmp[j];
    }

    public int reversePairs(int[] nums) {
        n = nums.length;
        this.nums = nums;
        tmp = new int[n];
        mergeSort(0, n - 1);
        return ans;
    }
}

到了这里，关于剑指 Offer 51. 数组中的逆序对的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！