[LeetCode]Reverse Pairs

这道题和之前的Count of Smaller Numbers after Self是一样的。同样有merge sort和BST两种解法，但是BST的解法没法过test case，是因为我们implement的并不是严格意义上的balanced binary search tree，最坏的情况可能到O(n^2)，所以我们用merge sort的解法来写，唯一不同的一点是对于i > j && 2 * nums[j] < nums[i]的才满足情况。我们在merge的时候也要做相应的调整，以half1 = {3,7,8}和half2 = {1,2,3}来举例，对于Count of Smaller Numbers after Self中的情况，也就是i > j && nums[j] < nums[i]，我们只需要在将half1中元素merge的时候统计half2已经被merge多少个元素(hi - (mid + 1))即可，这就是half1当前元素在这一轮当中找到的reverse pairs的数量。但是这道题的情况稍有不同，我们无法再用这种方法了，所以我们稍作改良，思路仍然一样，是运用双指针，假设p1,p2分别对应half1和half2的当前元素，我们在merge前先做一个预处理统计reverse pairs。我们移动p2直到其超过末尾或者nums[p2] * 2 >= nums[p1]，统计对于当前p1对应元素的reverse pairs，之后移动p1，重复以上步骤直到p1到达末尾，对于以上例子，步骤如下：

• p1指向3，p2指向2，reverse pairs = 1 {(3,1)}
• p1指向7，p2超出范围，reverse pairs = 1 + 3 {(7,1), (7,2), (7,3)}
• p1指向8，p2不变，reverse pairs = 4 + 3 {(8,1), (8,2), (8,3)}

这样的话我们可以在O(n)的时间完成统计和merge，时间复杂第O(n * log n)，代码如下：

	class Solution {
	public:
	int reversePairs(vector<int>& nums) {
	int len = nums.size(), res = 0;
	mergeSort(nums, res, 0, len - 1);
	return res;
	}
	private:
	void mergeSort(vector<int>& nums, int& res, int lo, int hi)
	{
	if(lo >= hi)return;
	int mid = lo + (hi - lo) / 2;
	mergeSort(nums, res, lo, mid);
	mergeSort(nums, res, mid + 1, hi);
	int p1 = lo, p2 = mid + 1;
	vector<int> aux(hi - lo + 1, 0);
	//count pairs
	while(p1 <= mid)
	{
	while(p2 <= hi && nums[p2] < nums[p1] / 2.0)
	++p2;
	res += p2 - mid - 1;
	++p1;
	}
	int curr = 0;
	p1 = lo, p2 = mid + 1;
	while (p1 <= mid || p2 <= hi)
	{
	if (p1 > mid) { aux[curr++] = nums[p2++]; continue; };
	if (p2 > hi) { aux[curr++] = nums[p1++]; continue; };
	if (nums[p1] <= nums[p2])aux[curr++] = nums[p1++];
	else aux[curr++] = nums[p2++];
	}
	for(int i = lo; i <= hi; ++i)
	nums[i] = aux[i - lo];
	}
	};

view raw Reverse Pairs.cpp hosted with ❤ by GitHub