LeetCode

LeetCode-merge应用-求逆序对

分治&归并

涉及到两两比较的操作，都可以考虑分治&归并。并归使得当前的对象两两比较完备，而分治使得两个分别两两比较后的对象之间两两比较，完备。

问题描述，求逆序对个数：[2,7,8,1,3,5]，比如其中的(2,7) (2,8) (2,3) (2,5)以2 开始的逆序对有4个。求一共有多少个逆序对。

思路：

如描述中的例子，当分制后，有[2,7,8]和[1,3,5]两部分，而2>1，所以以1为逆序对中第二个元素的逆序对有3个，(2,1) (7,1) (8,1)。这是因为并归操作的前提是两部分，分别有序。

核心是，当左部分第一个元素2大于右边第一个元素1时，count+=3，（2,7,8 有3个元素）。这是这个问题的关键！

实现：

看Merge操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void mergeOp_(vector<int>& nums, int l, int mid, int r){
    int* aux = new int[r-l+1];
    for (int i=l;i<=r;i++){
        aux[i-l]=nums[i];
    }

    int i=l;
    int j=mid+1;
    int b=j;
    for (int k=l;k<=r;k++){
        if (i>mid) { // 左边排玩
            nums[k]=aux[j-l];
            j++;
        }
        else if (j>r) { // 右边排完
            nums[k]=aux[i-l];
            i++;
        }
        else if (aux[i-l]<=aux[j-l]){
            nums[k] = aux[i-l];
            i++;
        } 
        // 左部分元素大于右部分元素时，记录逆序对个数
        else if(aux[i-l]>aux[j-l]){
            count_ += (b-i);  // 这里
            nums[k] = aux[j-l];
            j++;
        }
    }
    delete aux;
    aux=nullptr;
    return;
}

count_ += (b-i); 便是记录逆序对个数。

将上述操作放入下面code的完整的求逆序对解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Sol_mergeSort{
	int count_=0;

	void split_(vector<int>& nums, int l, int r){
		if (r<=l) return;
		int mid = (r-l)/2+l;
		split_(nums, l, mid);
		split_(nums, mid+1, r);
		mergeOp_(nums, l, mid, r);
		return;
	}

    // mergeOp_()

public:
	void mergeSort(vector<int>& nums){
		split_(nums, 0, nums.size()-1);
		return;
	}

	int count(){
		return count_;
	}
};

测试对象：{1,3,4,0,2,5}，逆序对有5对儿。

上述code结果： 

1
2
5  
0 1 2 3 4 5  // 排序后的结果

复杂度：O(N*longN)

敲黑板：从这个问题体会分治策略