專欄：算法的魔法世界

個人主頁：手握風云

目錄

一、歸并排序

二、例題講解

2.1.?排序數組

2.2.?交易逆序對的總數

2.3.?計算右側小于當前元素的個數

2.4.?翻轉對

---

一、歸并排序

? ? ? ? 歸并排序也是采用了分治的思想，將數組劃分為多個長度為1的子數組進行排序，再把多個子數組合并為最終的數組。

二、例題講解

2.1.?排序數組

? ? ? ? 我們再來回顧一下歸并排序的大體思路：以數組的中間值將數組劃分為兩個子數組，以此再繼續劃分，直至將數組劃分為里面只有一個元素，就可以向上返回。當左邊排完后，再去排右邊，然后再將兩個子數組進行合并，直到合并為原來的數組長度。

? ? ? ? 完整代碼實現：

class Solution {public int[] sortArray(int[] nums) {MergeSort(nums, 0, nums.length - 1);return nums;}private void MergeSort(int[] nums, int left, int right) {if (left >= right)return;//根據中間點劃分左右子數組int mid = (left + right) / 2;MergeSort(nums, left, mid);MergeSort(nums, mid + 1, right);//合并兩個有序數組int[] tmp = new int[right - left + 1];int p1 = left, p2 = mid + 1, i = 0;while (p1 <= mid && p2 <= right) {tmp[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];}while (p1 <= mid) {tmp[i++] = nums[p1++];}while (p2 <= right) {tmp[i++] = nums[p2++];}//還原for (int j = left; j <= right; j++) {nums[j] = tmp[j - left];}}
}

2.2.?交易逆序對的總數

? ? ? ? 暴力解法，利用兩層for循環，先固定其中一個數，再讓其他數與這個數進行比較，如果小，就讓計數器++。

class Solution {public int reversePairs(int[] record) {int count = 0;for(int i = 0;i < record.length;i ++){for(int j = i + 1;j < record.length;j++){if(record[i] > record[j]) count++;}}return count;}
}

? ? ? ? 第二種解法，將數組劃分為兩塊，先找出左區域的逆序對，再找出右區域的逆序對，最后再一左一右隨機挑一個數找出逆序對。但這樣的解法本質上還是一個暴力枚舉。我們接著來及逆行優化，我們先找完左區域的逆序對，然后對左區域進行排序；找完右區域的逆序對，然后對右區域進行排序。我們在左右區域里面隨機挑數的時候是不會影響逆序對的數量。

? ? ? ? 當我們在左右區域里面分別尋找逆序對時，如果數組長度較大，那么我們還可以再接著劃分，繼續按照上面的思路來找出逆序對的總數，這個部分就可以在遞歸中完成，所以我們在處理一左一右時也可以排個序。

? ? ? ? 接下來是查找子數組里面逆序對的數目，如下圖所示，p1左側是子數組中較小的元素，p2左側也是子數組中較小的元素。我們先固定p2這個數，接下來就是在[left,p1]這段區間里面尋找比p2大的元素。如果p1所指的元素比p2所指的元素小或者等于，那么就讓p1++；如果p1所指的元素比p2所指的元素大，那么p1后面的元素就都是比p2大，就可以快速的統計出數目，然后再讓p2++。

? ? ? ? 完整代碼實現：

class Solution {int[] tmp;public int reversePairs(int[] record) {int n = record.length;tmp = new int[n];return MergeSort(record, 0, n - 1);}private int MergeSort(int[] nums, int left, int right) {if (left >= right) return 0;int ret = 0;//中點元素int mid = (left + right) / 2;//左半部分的數目+右半部分的數目ret += MergeSort(nums, left, mid);ret += MergeSort(nums, mid + 1, right);//一左一右的數目int p1 = left, p2 = mid + 1, i = 0;while (p1 <= mid && p2 <= right) {if (nums[p1] <= nums[p2]) {tmp[i++] = nums[p1++];} else {ret += mid - p1 + 1;tmp[i++] = nums[p2++];}}while (p1 <= mid) tmp[i++] = nums[p1++];while (p2 <= right) tmp[i++] = nums[p2++];for (int j = left; j <= right; j++) {nums[j] = tmp[j - left];}return ret;}
}

2.3.?計算右側小于當前元素的個數

? ? ? ? 這道題要我們求出一個數組元素右邊有多少個數比它小，我們可以仿照上一題的思路，只不過這道題要把數組降序排列。

? ? ? ? 把數組分成兩部分，先找出左區域里面比自身小的個數，再找出右區域比自身小的個數，再一左一右去尋找個數。因為數組是降序排列的，所以p1、p2左邊都是相對較大的元素。如果nums[p1]<=nums[p2]，則p2++；如果nums[p1]>nums[p2]，因為我們最終是要返回一個順序表，所以我們要用該元素對應的位置來統計結果(right-p2+1)。但是經過歸并排序后，數組下標已經亂了，下一步就是要求數組元素對應的原始下標。

? ? ? ? 我們可以使用哈希思想來解決數組下標與元素的動態綁定，如果數組里面有重復元素，使用哈希表就很難。當對數組進行排序時，數組下標也要隨著變換。

? ? ? ? 完整代碼實現：

class Solution {int[] ret;int[] index;//標記原始下標int[] tmpIndex;//用于合并時的數組int[] tmpNum;public List<Integer> countSmaller(int[] nums) {int n = nums.length;ret = new int[n];index = new int[n];tmpIndex = new int[n];tmpNum = new int[n];//初始化index數組for (int i = 0; i < n; i++) {index[i] = i;}Mergesort(nums,0,n - 1);List<Integer> res = new ArrayList<>();for(int x : ret)res.add(x);return res;}private void Mergesort(int[] nums, int left, int right) {if(left >= right) return;//根據中間元素劃分區間int mid = (left + right) / 2;//處理左右區間Mergesort(nums,left,mid);Mergesort(nums,mid + 1,right);//合并int p1 = left,p2 = mid + 1,i = 0;while(p1 <= mid && p2 <= right){//降序if(nums[p1] <= nums[p2]){tmpNum[i] = nums[p2];tmpIndex[i++] = index[p2++];} else {ret[index[p1]] += right - p2 + 1;tmpNum[i] = nums[p1];tmpIndex[i++] = index[p1++];}}//處理剩余的排序while(p1 <= mid){tmpNum[i] = nums[p1];tmpIndex[i++] = index[p1++];}while(p2 <= right){tmpNum[i] = nums[p2];tmpIndex[i++] = index[p2++];}for (int j = left; j <= right; j++) {nums[j] = tmpNum[j - left];index[j] = tmpIndex[j - left];}}
}

2.4.?翻轉對

? ? ? ? 我們依然可以按照逆序對那道題，將數組劃分為兩塊，求出左區域、右區域以及一左一右的翻轉對的和。但是逆序對那道題是1:1進行比較的，而這道題需要前面的元素大于后面元素的2倍，就不能按照歸并排序的思路來解決。所以我們先計算翻轉對的數目，我們可以有兩種思路：1.計算當前元素后面，有多少元素的2倍比該數小；2.計算當前元素后面，有多少元素的一半比該數大。

? ? ? ? 我們先來講下方法1（按照降序排列，沒有邊界）：利用數組有序的特性計算翻轉對。如果nums[p1]<=nums[p2]，p2向后移動，直到nums[p1]>nums[p2]時，就可以統計出數目來。如果我們讓p2回退，那么時間復雜度就會達到級別。因為數組是降序的，當p1右移時，所指向的元素也會變小，沒必要再讓p2回退，就可以構成同向雙指針了。方法2也同理，如果nums[p1]>= nums[p2]，就讓p1向右移動，直到nums[p1]<nums[p2]，再讓p2向右移動，p1同樣不用回退。

? ? ? ? 完整代碼實現：

class Solution {int[] tmp;public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];return Mergesort(nums,0,n - 1);}private int Mergesort(int[] nums, int left, int right) {if(left >= right) return 0;int ret = 0;int mid = (left + right) / 2;ret += Mergesort(nums,left,mid);ret += Mergesort(nums,mid + 1,right);int p1 = left,p2 = mid + 1,i = left;while(p1 <= mid) {while (p2 <= right && nums[p2] >= nums[p1] / 2.0) p2++;if(p2 > right)break;ret += right - p2 + 1;p1++;}p1 = left;p2 = mid + 1;while(p1 <= mid && p2 <= right){tmp[i++] = (nums[p1] <= nums[p2]) ? nums[p2++] : nums[p1++];}while(p1 <= mid) tmp[i++] = nums[p1++];while(p2 <= right) tmp[i++] = nums[p2++];for (int j = left; j <= right; j++) {nums[j] = tmp[j];}return ret;}
}