可以借助歸并排序秒殺的面試題！

哎嘛，這假期過的可真快啊，又要早起搬磚了，那咱們就接著來做題吧，牛年一起沖沖沖！咱們今天繼續(xù)說歸并排序。

歸并排序是面試的高頻考點，下面我們來一起看看如何借助歸并排序解決逆序?qū)ΓD(zhuǎn)對問題。在 leetcode 上面屬于困難題目。

大家做題之前可以順便解決一下這個題目，leetcode 912 排序數(shù)組，這個題目大家可以用來練手，因為有些排序算法是面試高頻考點，所以大家可以多用這個題目進(jìn)行練習(xí)，防止手生。

下面則是我寫文章時代碼的提交情況，冒泡排序怎么優(yōu)化都會超時，其他排序算法倒是都可以通過。

下面我們一起來看一下，如何利用歸并排序來解決逆序?qū)栴}，其實很簡單，我們僅僅需要在之前的歸并排序添加一行代碼即可，我們首先來看一下什么是逆序?qū)?。繼續(xù)用之前的例子。

逆序?qū)Γ涸跀?shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)?，見下圖。

逆序?qū)?/figcaption>

是不是很容易理解，因為數(shù)組是無序的，當(dāng)較大的數(shù)，出現(xiàn)在較小數(shù)前面的時候，它倆則可以組成逆序?qū)Α?/span>

數(shù)組的（有序度+逆序度）= ?n (n-1) / 2，n代表元素個數(shù)，逆序?qū)€數(shù) = 數(shù)組的逆序度，有序?qū)€數(shù) = 數(shù)組的有序度，所以我們知道有序?qū)€數(shù)的話，自然能得到逆序?qū)Φ膫€數(shù)。

那么我們?nèi)绾瓮ㄟ^歸并排序來計算逆序?qū)€數(shù)呢？

關(guān)鍵點在我們的歸并過程中，我們先來看下歸并過程中是怎么計算逆序?qū)€數(shù)的。見下圖

我們來拆解下上圖，我們此時 ?temp1 指向元素為 6，temp2 指向元素為 2, nums[temp1] > temp[temp2]。

則此時我們需要將 temp2 指向的元素存入臨時數(shù)組中，又因為每個小集合中的元素都是有序的，所以 temp1 后面的元素也一定大于 2。那么我們就可以根據(jù) temp1 的索引得出當(dāng)前情況下的逆序?qū)€數(shù)，則是 mid - temp1 + 1。

好啦這個題目你已經(jīng)會做啦，下面我們一起來做下吧。

? ?劍指 Offer 51. 數(shù)組中的逆序?qū)?/strong>

題目描述

在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)?。輸入一個數(shù)組，求出這個數(shù)組中的逆序?qū)Φ目倲?shù)。

示例 1:

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

題目解析

各位如果忘記歸并排序的話，可以再看一下咱們之前的文章回顧一下 歸并排序詳解，這個題目我們僅僅在歸并排序的基礎(chǔ)上加了一行代碼。那就是在歸并過程時，nums[temp2] ?< nums[temp1] 時統(tǒng)計個數(shù)。下面我們直接看代碼吧。

題目代碼

class?Solution?{
????//全局變量
????private?int?count;?
????public?int?reversePairs(int[]?nums)?{
?????????count?=?0;??????
?????????merge(nums,0,nums.length-1);
?????????return?count;
????}

????public?void?merge?(int[]?nums,?int?left,?int?right)?{

????????if?(left?????????????int?mid?=?left?+?((right?-?left)?>>?1);
????????????merge(nums,left,mid);
????????????merge(nums,mid+1,right);
????????????mergeSort(nums,left,mid,right);
????????}

????}

????public?void?mergeSort(int[]?nums,?int?left,?int?mid,?int?right)?{

?????????int[]?temparr?=?new?int[right-left+1];
?????????int?index?=?0;
?????????int?temp1?=?left,?temp2?=?mid+1;

?????????while?(temp1?<=?mid?&&?temp2?<=?right)?{

?????????????if?(nums[temp1]?<=?nums[temp2])?{
?????????????????temparr[index++]?=?nums[temp1++];
?????????????}?else?{
?????????????????//增加的一行代碼，用來統(tǒng)計逆序?qū)€數(shù)
?????????????????count?+=?(mid?-?temp1?+?1);
?????????????????temparr[index++]?=?nums[temp2++];
?????????????}
?????????}

?????????if?(temp1?<=?mid)?System.arraycopy(nums,temp1,temparr,index,mid-temp1+1);
?????????if?(temp2?<=?right)?System.arraycopy(nums,temp2,temparr,index,right-temp2+1);
?????????System.arraycopy(temparr,0,nums,left,right-left+1);
????}
}

好啦，這個題目我們就解決啦，哦對，大家也可以順手去解決下這個題目。

下面我們繼續(xù)解決翻轉(zhuǎn)對問題，也完全可以用歸并排序解決，稍微加了一丟丟代碼，也是很好理解的。

? ?leetcode 493. 翻轉(zhuǎn)對

題目描述

給定一個數(shù)組 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我們就將 (i, j) 稱作一個重要翻轉(zhuǎn)對。

你需要返回給定數(shù)組中的重要翻轉(zhuǎn)對的數(shù)量。

示例 1:

輸入: [1,3,2,3,1]
輸出: 2

示例 2:

輸入: [2,4,3,5,1]
輸出: 3

題目解析

我們理解了逆序?qū)Φ暮x之后，題目理解起來完全沒有壓力的，這個題目第一想法可能就是用暴力法解決，但是會超時，所以我們有沒有辦法利用歸并排序來完成呢？

我們繼續(xù)回顧一下歸并排序的歸并過程，兩個小集合是有序的，然后我們需要將小集合歸并到大集合中，則我們完全可以在歸并之前，先統(tǒng)計一下翻轉(zhuǎn)對的個數(shù)，然后再進(jìn)行歸并，則最后排序完成之后自然也就得出了翻轉(zhuǎn)對的個數(shù)。具體過程見下圖。

此時我們發(fā)現(xiàn) 6 > 2 * 2，所以此時是符合情況的，因為小數(shù)組是單調(diào)遞增的，所以 6 后面的元素都符合條件，所以我們 count += mid - temp1 + 1；則我們需要移動紫色指針，判斷 2 的后面是否還存在符合條件的情況。

我們此時發(fā)現(xiàn) ?6 = 3 * 2，不符合情況，因為小數(shù)組都是完全有序的，所以后面沒有符合條件的情況了，則我們可以移動紅色指針，看 6 后面的數(shù)有沒有符合條件的情況，重復(fù)上訴過程，直至遍歷結(jié)束。

這樣我們就可以得到翻轉(zhuǎn)對的數(shù)目啦。

大家思考一下為什么我們不可以和逆序?qū)σ粯釉跉w并到大集合時統(tǒng)計？

可以看一下這個樣例兩個小集合分別是[-5,-2,1],[-4,-3,5],如果不進(jìn)行遍歷統(tǒng)計，只在合并時統(tǒng)計，則會漏掉某些情況。

下面我們直接看視頻加深下印象吧！

是不是很容易理解啊，那我們直接看代碼吧，僅僅是在歸并排序的基礎(chǔ)上加了幾行代碼用于統(tǒng)計翻轉(zhuǎn)對。

題目代碼

class?Solution?{
????private?int?count;

????public?int?reversePairs(int[]?nums)?{
????????count?=?0;
????????merge(nums,?0,?nums.length?-?1);
????????return?count;
????}

????public?void?merge(int[]?nums,?int?left,?int?right)?{

????????if?(left?????????????int?mid?=?left?+?((right?-?left)?>>?1);
????????????merge(nums,?left,?mid);
????????????merge(nums,?mid?+?1,?right);
????????????mergeSort(nums,?left,?mid,?right);
????????}

????}

????public?void?mergeSort(int[]?nums,?int?left,?int?mid,?int?right)?{

????????int[]?temparr?=?new?int[right?-?left?+?1];
????????int?temp1?=?left,?temp2?=?mid?+?1,?index?=?0;
????????//計算翻轉(zhuǎn)對
????????while?(temp1?<=?mid?&&?temp2?<=?right)?{
????????????//這里需要防止溢出
????????????if?(nums[temp1]?>?2?*?(long)?nums[temp2])?{
????????????????count?+=?mid?-?temp1?+?1;
????????????????temp2++;
????????????}?else?{
????????????????temp1++;
????????????}
????????}
????????//記得歸位，我們還要繼續(xù)使用
????????temp1?=?left;
????????temp2?=?mid?+?1;
????????//歸并排序
????????while?(temp1?<=?mid?&&?temp2?<=?right)?{

????????????if?(nums[temp1]?<=?nums[temp2])?{
????????????????temparr[index++]?=?nums[temp1++];
????????????}?else?{
????????????????temparr[index++]?=?nums[temp2++];
????????????}
????????}
????????//照舊
????????if?(temp1?<=?mid)?System.arraycopy(nums,?temp1,?temparr,?index,?mid?-?temp1?+?1);
????????if?(temp2?<=?right)?System.arraycopy(nums,?temp2,?temparr,?index,?right?-?temp2?+?1);
????????System.arraycopy(temparr,?0,?nums,?left,?right?-?left?+?1);
????}
}