目錄

題目：劍指 Offer 51. 數(shù)組中的逆序?qū)?- 力扣（Leetcode）

題目的接口：

解題思路：

代碼：

過啦?。?！

寫在最后：

題目：劍指 Offer 51. 數(shù)組中的逆序?qū)?- 力扣（Leetcode）

題目的接口：

class Solution {
public:
    int reversePairs(vector<int>& nums) {

    }
};

解題思路：

這一道題，我的思路是用雙指針暴力求解，

但這個數(shù)組長度，O(N^2)的時間復(fù)雜度肯定是不可能把所有樣例跑完，

看了大佬的思路，用的是歸并排序，（如果不會歸并排序，最好先去學(xué)一下）

我一開始看了很久沒有搞明白為什么，

實際上，這個思路是利用的歸并排序的一個特性，具體思路如下：

例： 數(shù)組 [ 7, 5, 2, 6, 0, 1, 5, 4 ]

我們就拿這個數(shù)組歸并到最后一步的時候作為樣例：

[ 2, 5, 6, 7 ] 和?[ 0, 1, 4, 5 ]

由于他們通過先前的歸并已經(jīng)是兩個有序的數(shù)組，

而最后一步就兩個數(shù)組每個元素比大小，然后尾插到臨時數(shù)組上，最后再拷貝回來，

重點來了：

第一個數(shù)比大小 2 > 0 所以尾插 0 并讓第二個數(shù)組的下標(biāo)begin2++，

因為這兩個是升序數(shù)組，2 > 0，也表明 2 之后的所有數(shù)都大于 0 ,

那么這里就有 4 ( mid + 1，也就是第一個數(shù)組的長度) 個逆序數(shù)對，

那么，當(dāng) 2 和 4 比較，2 < 4 ，就尾插 2 進臨時數(shù)組，讓第一個數(shù)組下標(biāo)begin1++，

這個時候，繼續(xù)往下比較，5 > 4，?尾插 4?并讓第二個數(shù)組的下標(biāo)begin2++，

因為這兩個是升序數(shù)組，5?> 4，也表明 5?之后的所有數(shù)都大于 4，

但是因為第一個數(shù)組已經(jīng)是第二個數(shù)了，所以：

這里就有 3 （ mid + 1 - begin1?（也就是減去第一個數(shù)組的下標(biāo)））個逆序數(shù)對。

綜上所述，

我們只需要在第一個數(shù)組的值 > 第二個數(shù)組的值的時候，記錄逆序數(shù)對?(mid + 1 - begin1) 即可。

下面是代碼：

代碼：

class Solution {
public:
    //計數(shù)
    int res = 0;
    int reversePairs(vector<int>& nums) {
        //創(chuàng)建臨時數(shù)組
        vector<int> tmp(nums.size());
        //歸并排序，我用的是我學(xué)的歸并排序模板
        merge_sort(nums, tmp, 0, nums.size() - 1);
        return res;
    }
private:
    void merge_sort(vector<int>& nums, vector<int>& tmp, int begin, int end) {
        if(begin >= end) return; //返回

        //分治
        int mid = (begin + end) >> 1;
        merge_sort(nums, tmp, begin, mid);
        merge_sort(nums, tmp, mid + 1, end);
        //[begin][mid], [mid + 1][end]

        //兩個數(shù)組的下標(biāo)
        int begin1 = begin, end1 = mid;
        int begin2 = mid + 1, end2 = end;

        //臨時數(shù)組的下標(biāo)
        int i = begin;

        //比較大小之后尾插進臨時數(shù)組
        while(begin1 <= end1 && begin2 <= end2) {
            if(nums[begin1] <= nums[begin2]) {
                tmp[i++] = nums[begin1++];
            }
            else {
                tmp[i++] = nums[begin2++];
                //計算這一段的逆序數(shù)對數(shù)量//具體推導(dǎo)看文章的文字
                res += mid + 1 - begin1; //整個思路的核心
            }
        }

        //將沒有插完的值全部尾插進臨時數(shù)組
        while(begin1 <= end1) tmp[i++] = nums[begin1++];
        while(begin2 <= end2) tmp[i++] = nums[begin2++];

        //將臨時數(shù)組拷貝回原數(shù)組
        for(int i = begin; i <= end; i++) {
            nums[i] = tmp[i];
        }
    }
};

過啦?。?！

?

寫在最后：

以上就是本篇文章的內(nèi)容了，感謝你的閱讀。

如果喜歡本文的話，歡迎點贊和評論，寫下你的見解。

如果想和我一起學(xué)習(xí)編程，不妨點個關(guān)注，我們一起學(xué)習(xí)，一同成長。

之后我還會輸出更多高質(zhì)量內(nèi)容，歡迎收看文章來源地址http://www.zghlxwxcb.cn/news/detail-410426.html

到了這里，關(guān)于【LeetCode】劍指 Offer（26）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！