逆序對的計數

從自己的部落格轉載。

leetcode#493題，給定一個數組A，尋找i<j，但是有A[i]>A[j]的數目。變種為重要逆序對的尋找即尋找A[i]>kA[j]的數目。

題目來源：https://leetcode.com/problems/reverse-pairs/

解題思路

基本的逆序對與重要逆序對思路一緻，是以隻對逆序對進行講解。

暴力枚舉

從前往後周遊數組，枚舉出所有(A[i],A[j])，然後統計符合條件的重要逆序對的數目，很明顯所需要的時間複雜度為

O ( n 2 ) O(n^2) O(n2)

分治

分析

先考慮最簡單的情況：

如果input的數組長度為n=1，則輸出為0，不存在逆序對。會做

n=2的時候，可以分解成兩個n=1的情況。因為左右兩邊都是一個元素自然都不存在逆序對，考慮一個元素在左邊，一個在右邊的情況可以得出(8,4)一個逆序對的情況，是以輸出為1。會做

n=4的時候：同樣的可以分解成兩個n=2的情況，因為我們已經解決了n=2的問題。這時候左邊數組存在一個(8,4)的逆序對，右邊數組存在一個(3,2)的逆序對。這時候主要考慮的是交叉的情況，如果左右兩個數組都是沒有結構的，那麼隻能用兩個指針來挨個周遊左右兩邊的數組了時間複雜度為 O ( n 2 ) O(n^2) O(n2) 。如果左右兩邊數組都是有序的情況下，就可以減少很多備援的比較操作了，當 L i > R j L_i>R_j Li​>Rj​ 時，左邊數組位于 L i L_i Li​ 後面的元素肯定都會大于 R j R_j Rj​ ，是以就不用在比較 L i L_i Li​ 後面的元素了,将右邊數組指針+1尋找更大的元素來進行比較。當 L i < R j L_i<R_j Li​<Rj​時，需要将左邊的指針+1，尋找一個更大的左邊元素進行比較。因為左右指針總共的移動次數不超過數組長度，是以這時的複雜度為 O ( n ) O(n) O(n)。以圖中的例子來說明，當有4大于3的時候，就不需要比較8是否大于3了。

一個形象的比喻是兩個人打牌，一個人L拿的是左邊的數組，另一個人R是右邊的數組，牌已經從小到大整理好了。如果L最小的牌比R的最小的牌都大，那麼L手中所有的牌都比R的最小的牌大。R要找到比L目前牌更大的牌隻能向後尋找，如果找不到說明，L所有的牌都比R大，如果找到了是 R j R_j Rj​那麼L就向後面再找一個新的比 R j R_j Rj​的牌大的新牌 L i L_i Li​ 。規則就是從左到右出牌，牌小的先出，最後誰的牌出完那麼遊戲結束，結束逆序對的統計。

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-TtHbu4eW-1574914055448)(https://res.cloudinary.com/bravey/image/upload/v1570434502/blog/reversepairs.jpg)]

歸納

可以看到，在上述分析過程中我們可以将輸入為n的數組不斷劃分為原來的一半直至最後n=1的情況，從n=1的情況再向上合并得到上層問題的答案，也就是歸并排序的過程中加上了逆序對的統計，這是一個很典型的分治政策。

Divide 将輸入數組A劃分為左邊A[0, n/2] 與右邊A[n/2+1, n-1]兩個數組

Conquer 左邊的逆序對數目與右邊的逆序對數目分别再各自遞歸的調用函數求解，同時對其排序。

Merge 統計逆序對元素交叉在左右兩邊的情況，并将兩個排好序的子數組合并成一個新的有序數組

複雜度

将規模為n的問題分解成兩個兩個 n 2 \frac{n}{2} 2n​ 的子問題問題，同時對兩個子問題進行合并的複雜度為O(n)，是以有遞推公式：

KaTeX parse error: Unknown column alignment: * at position 31: … \begin{array}{*̲*lr**} …

根據主定理有最後的複雜度為 O ( n log ⁡ ( n ) ) O(n\log(n)) O(nlog(n))

代碼

/*
https://leetcode.com/problems/reverse-pairs/
 */
#include <iostream>
#include <vector>
using namespace std;
class Solution {
	vector<int> tmp_vec;//把tmp_vec設定成共有變量，而不在函數中設定為臨時變量可以減少多次對其建立與銷毀，提高效率
public:
    int reversePairs(vector<int>& nums) {
    	int size = nums.size();
    	tmp_vec.resize(nums.size());
        return MergeSort(nums, 0, size-1); // 不用全局變量否則，多線程的時候會被修改。
    }

private:
	int MergeSort(vector<int>& vec, int lo, int hi){
		if(lo>=hi) return 0;// base case 遞歸必備
		int mid = lo + (hi -lo)/2; //防止兩個超級大的int相加後造成溢出
		int ans = 0;
		ans += MergeSort(vec, lo, mid); //左邊merge的計數
		ans += MergeSort(vec, mid+1, hi); //右邊merge的計數
		ans += Merge(vec, lo, hi, mid);// 傳回什麼？ 本次merge的技術 也就是split 的情況
		return ans;
	}

	int Merge(vector<int>& vec, int lo, int hi, int mid){ //采用雙指針來一次把左右兩邊的小值冒泡出來放到合并後的數組中，同時完成對逆序數目的統計
		int p = lo;
		int q = mid + 1;
		int count = 0;//記錄逆序數目
		int index = lo;
		while(p<=mid&&q<=hi){
			if((long)vec[p] > (long)vec[q]*3){
				count += mid-p+1;
				q++;
			}else{
				p++;
			}
		}
		//正常的merge操作
		p = lo ;
		q = mid + 1;
		while(p<=mid&&q<=hi){
			if(vec[p]>=vec[q]) tmp_vec[index++]=vec[q++];
			else tmp_vec[index++]=vec[p++];
		}
		while(p<=mid) tmp_vec[index++]=vec[p++];
		while(q<=hi) tmp_vec[index++]=vec[q++];
		for(int i=lo; i<=hi; i++){
			vec[i] = tmp_vec[i];
		}
		return count;
	}    
};

int main(){
	Solution Sol;
	vector<int> vec;
	int n ;
	while(cin>>n){
		//int tmp = n;
		int element;
		while(n--){
			cin>>element;
			vec.push_back(element);
		}
		cout<<Sol.reversePairs(vec)<<endl;
	}
	
}