欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer 51:数组中的逆序对

程序员文章站 2022-07-10 12:16:58
...

可以用归并排序的思想,在合并两个字数组时计算下逆序对数目,并加在一起。

class Solution {
public:
	void Merge(vector<int> & data, long long & result, int start, int mid, int end)
	{
		int num = end - start + 1;
		int len1 = mid - start + 1;
		int len2 = end - mid;

		vector<int > temp(num, 0);
		int index1 = mid;
		int index2 = end;
		for (int index = num - 1; index >= 0; index--)
		{
			if (data[index1]>data[index2])
			{
				temp[index] = data[index1];
				index1--;
				result = result + index2-mid;
			}
			else
			{
				temp[index] = data[index2];
				index2--;
			}

			if (index1<start)
			{
				index--;
				while (index2>mid)
				{
					temp[index] = data[index2];
					index--;
					index2--;
				}
				break;
			}
			if (index2<mid+1)
			{
				index--;
				while (index1>=start)
				{
					temp[index] = data[index1];
					index--;
					index1--;
				}
				break;
			}
		}
		for (int i = 0; i<num; i++)
			data[start + i] = temp[i];
	}
	void MergeSort(vector<int> & data, long long & result, int start, int end)
	{
		if (start == end)
			return;
		int mid = start + (end - start) / 2;
		MergeSort(data, result, start, mid);
		MergeSort(data, result, mid + 1, end);
		Merge(data, result, start, mid, end);
	}
	int InversePairs(vector<int> data) {
		long long result = 0;
		int len = data.size();
		if (len<1)
			return result;

		MergeSort(data, result, 0, data.size() - 1);

		return result % 1000000007;
	}
};