微軟面試題:劍指 Offer 51. 數組中的逆序對 Hard 出現次數:3

題目描述:

在數組中的兩個數字,如果前面一個數字大於後面的數字,則這兩個數字組成一個逆序對。

輸入一個數組,求出這個數組中的逆序對的總數。

示例 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 };