微軟面試題：劍指 Offer 51. 數組中的逆序對 Hard 出現次數：3
- 2020 年 12 月 9 日
- 筆記
- LeetCode_分治, LeetCode_雙指針, 微軟面試
題目描述：
在數組中的兩個數字，如果前面一個數字大於後面的數字，則這兩個數字組成一個逆序對。
輸入一個數組，求出這個數組中的逆序對的總數。
示例 1:
輸入: [7,5,6,4] 輸出: 5
限制：
0 <= 數組長度 <= 50000
分析：
本題的暴力方法顯然容易想到，但是會報超時，難度等級 hard 顯示 考察的是使用
時間O（log n*logn）空間 O(n)的解法。可以使用 「歸併排序」 和 「線段樹」 兩種方法。
利用「歸併排序」和「線段樹」計算逆序對都是非常經典的做法。這裡我們暫且只考慮
利用「歸併排序」計算逆序對。
思想是「分治算法」，所有的「逆序對」來源於 3 個部分：
- 左邊區間的逆序對；
- 右邊區間的逆序對；
- 橫跨兩個區間的逆序對。
計算左邊區間的逆序對和右邊區間的逆序對都是規模更小的子問題，直接交給遞歸去完成。
重點是分析計算橫跨兩個區間的逆序對。計算橫跨兩個區間的逆序對時，上面的兩個子問題都已經讓遞歸函數完成了，
此時，左邊區間的逆序對和右邊區間的逆序對都已經計算出來了，且左邊區間和右邊區間都已經有序了。
計算橫跨兩個區間的逆序對 具體步驟如下：
1. 將給定區間 nums[l,r] 分成 左區間 nums[l , mid] ,右區間 nums[mid + 1,r] ,使用雙指針同步遍歷左右區間；
2. 如果左邊區間當前的元素num[i] 小於等於 右邊區間當前的元素nums [j]，因為nums[i] 小於等於右邊區間
所有的元素nums[j,r]，nums[i] 不會和右區間內的元素nums[j,r] 構成逆序對。直接將nums[i] 放入歸併排序的輔助空間。
3. 如果左邊區間當前的元素num[i] 大於 右邊區間當前的元素nums [j]，那左邊區間元素num[i,mid] ，一共 mid – i + 1 個都比
右邊區間當前的元素nums[j]大，且都在右邊區間當前的元素前面，和右邊區間當前元素 構成 mid – i + 1 個逆序對。
加到總的逆序對數上，再將右邊區間當前的元素nums [j] 放到緩衝區。
3. 將左（右）區間比較多出來的元素直接加到輔助空間中.
4. 將輔助空間中排序好的元素 再重新放回nums[l,r];
5. 函數返回當前區間計算得到的總的逆序對數。
代碼如下：
1 class Solution { 2 public: 3 vector<int> tmp;//歸併排序的輔助數組 4 5 int reversePairs(vector<int>& nums) { 6 tmp.assign(nums.size(),0); 7 return merge_sort(nums,0,nums.size() - 1); 8 } 9 10 long long int merge_sort(vector<int>& nums,int l,int r) 11 { 12 if(l >= r)//歸併排序遞歸出口 13 { 14 return 0; 15 } 16 int mid = l + (r - l)/2;//將區間一分為二 17 long long ans = merge_sort(nums,l,mid) + merge_sort(nums,mid + 1,r);//遞歸地求左右子數組的逆序對個數和 18 int k = 0,i = l,j = mid + 1;//計算 橫跨左右區間的逆序對 19 while(i <= mid && j <= r) 20 { 21 if(nums[i] <= nums[j]) 22 { 23 tmp[k++] = nums[i++]; 24 } 25 else 26 { //執行上述遞歸之後，左右子數組都已經排好序 27 //nums[i:mid] 都比nums[j] 大，都和num[j] 構成逆序對 28 ans += (mid - i + 1); 29 tmp[k++] = nums[j++]; 30 } 31 } 32 while(i <= mid) tmp[k++] = nums[i++]; 33 while(j <= r) tmp[k++] = nums[j++]; 34 //將排序好的元素移回原數組，放在原來的區間上 35 for(i = l,j = 0;i <= r; ) 36 { 37 nums[i++] = tmp[j++]; 38 } 39 return ans; 40 } 41 };
