可以藉助歸併排序秒殺的面試題！
歸併排序是面試的高頻考點，下面我們來一起看看如何藉助歸併排序解決逆序對，翻轉對問題。在 leetcode 上面屬於困難題目。
大家做題之前可以順便解決一下這個題目，leetcode 912 排序數組，這個題目大家可以用來練手，因爲有些排序算法是面試高頻考點，所以大家可以多用這個題目進行練習，防止手生。
下面則是我寫文章時代碼的提交情況，冒泡排序怎麼優化都會超時，其他排序算法倒是都可以通過。
下面我們一起來看一下，如何利用歸併排序來解決逆序對問題，其實很簡單，我們僅僅需要在之前的歸併排序添加一行代碼即可，我們首先來看一下什麼是逆序對。繼續用之前的例子。
逆序對：在數組中的兩個數字，如果前面一個數字大於後面的數字，則這兩個數字組成一個逆序對，見下圖。
逆序對
是不是很容易理解，因爲數組是無序的，當較大的數，出現在較小數前面的時候，它倆則可以組成逆序對。
數組的（有序度 + 逆序度）= n (n-1) / 2，n 代表元素個數，逆序對個數 = 數組的逆序度，有序對個數 = 數組的有序度，所以我們知道有序對個數的話，自然能得到逆序對的個數。
那麼我們如何通過歸併排序來計算逆序對個數呢？
關鍵點在我們的歸併過程中，我們先來看下歸併過程中是怎麼計算逆序對個數的。見下圖
逆序對舉例
我們來拆解下上圖，我們此時 temp1 指向元素爲 6，temp2 指向元素爲 2, nums[temp1] > temp[temp2]。
則此時我們需要將 temp2 指向的元素存入臨時數組中，又因爲每個小集合中的元素都是有序的，所以 temp1 後面的元素也一定大於 2。那麼我們就可以根據 temp1 的索引得出當前情況下的逆序對個數，則是 mid - temp1 + 1。
好啦這個題目你已經會做啦，下面我們一起來做下吧。
劍指 Offer 51. 數組中的逆序對
題目描述
在數組中的兩個數字，如果前面一個數字大於後面的數字，則這兩個數字組成一個逆序對。輸入一個數組，求出這個數組中的逆序對的總數。
示例 1:
輸入: [7,5,6,4]
輸出: 5
題目解析
各位如果忘記歸併排序的話，可以再看一下咱們之前的文章回顧一下 歸併排序詳解，這個題目我們僅僅在歸併排序的基礎上加了一行代碼。那就是在歸併過程時，nums[temp2] < nums[temp1] 時統計個數。下面我們直接看代碼吧。
題目代碼
1class Solution {
2 //全局變量
3 private int count;
4 public int reversePairs(int[] nums) {
5 count = 0;
6 merge(nums,0,nums.length-1);
7 return count;
8 }
9
10 public void merge (int[] nums, int left, int right) {
11
12 if (left < right) {
13 int mid = left + ((right - left) >> 1);
14 merge(nums,left,mid);
15 merge(nums,mid+1,right);
16 mergeSort(nums,left,mid,right);
17 }
18
19 }
20
21 public void mergeSort(int[] nums, int left, int mid, int right) {
22
23 int[] temparr = new int[right-left+1];
24 int index = 0;
25 int temp1 = left, temp2 = mid+1;
26
27 while (temp1 <= mid && temp2 <= right) {
28
29 if (nums[temp1] <= nums[temp2]) {
30 temparr[index++] = nums[temp1++];
31 } else {
32 //增加的一行代碼，用來統計逆序對個數
33 count += (mid - temp1 + 1);
34 temparr[index++] = nums[temp2++];
35 }
36 }
37
38 if (temp1 <= mid) System.arraycopy(nums,temp1,temparr,index,mid-temp1+1);
39 if (temp2 <= right) System.arraycopy(nums,temp2,temparr,index,right-temp2+1);
40 System.arraycopy(temparr,0,nums,left,right-left+1);
41 }
42}
43
44
好啦，這個題目我們就解決啦，哦對，大家也可以順手去解決下這個題目。
下面我們繼續解決翻轉對問題，也完全可以用歸併排序解決，稍微加了一丟丟代碼，也是很好理解的。
leetcode 493. 翻轉對
題目描述
給定一個數組 nums ，如果 i <j 且 nums[i] > 2*nums[j] 我們就將 (i, j) 稱作一個重要翻轉對。
你需要返回給定數組中的重要翻轉對的數量。
示例 1:
輸入: [1,3,2,3,1]
輸出: 2
示例 2:
輸入: [2,4,3,5,1]
輸出: 3
題目解析
我們理解了逆序對的含義之後，題目理解起來完全沒有壓力的，這個題目第一想法可能就是用暴力法解決，但是會超時，所以我們有沒有辦法利用歸併排序來完成呢？
我們繼續回顧一下歸併排序的歸併過程，兩個小集合是有序的，然後我們需要將小集合歸併到大集合中，則我們完全可以在歸併之前，先統計一下翻轉對的個數，然後再進行歸併，則最後排序完成之後自然也就得出了翻轉對的個數。具體過程見下圖。
翻轉對
此時我們發現 6 > 2 * 2，所以此時是符合情況的，因爲小數組是單調遞增的，所以 6 後面的元素都符合條件，所以我們 count += mid - temp1 + 1；則我們需要移動紫色指針，判斷 2 的後面是否還存在符合條件的情況。
翻轉對
我們此時發現 6 = 3 * 2，不符合情況，因爲小數組都是完全有序的，所以後面沒有符合條件的情況了，則我們可以移動紅色指針，看 6 後面的數有沒有符合條件的情況，重複上訴過程，直至遍歷結束。
這樣我們就可以得到翻轉對的數目啦。
大家思考一下爲什麼我們不可以和逆序對一樣在歸併到大集合時統計？
可以看一下這個樣例兩個小集合分別是 [-5,-2,1],[-4,-3,5], 如果不進行遍歷統計，只在合併時統計，則會漏掉某些情況。
下面我們直接看視頻加深下印象吧！
是不是很容易理解啊，那我們直接看代碼吧，僅僅是在歸併排序的基礎上加了幾行代碼用於統計翻轉對。
題目代碼
1class Solution {
2 private int count;
3
4 public int reversePairs(int[] nums) {
5 count = 0;
6 merge(nums, 0, nums.length - 1);
7 return count;
8 }
9
10 public void merge(int[] nums, int left, int right) {
11
12 if (left < right) {
13 int mid = left + ((right - left) >> 1);
14 merge(nums, left, mid);
15 merge(nums, mid + 1, right);
16 mergeSort(nums, left, mid, right);
17 }
18
19 }
20
21 public void mergeSort(int[] nums, int left, int mid, int right) {
22
23 int[] temparr = new int[right - left + 1];
24 int temp1 = left, temp2 = mid + 1, index = 0;
25 //計算翻轉對
26 while (temp1 <= mid && temp2 <= right) {
27 //這裏需要防止溢出
28 if (nums[temp1] > 2 * (long) nums[temp2]) {
29 count += mid - temp1 + 1;
30 temp2++;
31 } else {
32 temp1++;
33 }
34 }
35 //記得歸位，我們還要繼續使用
36 temp1 = left;
37 temp2 = mid + 1;
38 //歸併排序
39 while (temp1 <= mid && temp2 <= right) {
40
41 if (nums[temp1] <= nums[temp2]) {
42 temparr[index++] = nums[temp1++];
43 } else {
44 temparr[index++] = nums[temp2++];
45 }
46 }
47 //照舊
48 if (temp1 <= mid) System.arraycopy(nums, temp1, temparr, index, mid - temp1 + 1);
49 if (temp2 <= right) System.arraycopy(nums, temp2, temparr, index, right - temp2 + 1);
50 System.arraycopy(temparr, 0, nums, left, right - left + 1);
51 }
52}
53
54
好啦，我們的文章到這就結束啦，希望對你有一丟丟幫助啊。是不是覺得這兩個困難題很簡單啊，大家可以去寫一下啦。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/vVmbjvqQeiC2pOzawexHKw