剑指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;
}
};
推荐阅读
-
剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)
-
剑指offer28:找出数组中超过一半的数字。
-
剑指offer27:按字典序打印出该字符串中字符的所有排列
-
C#版剑指Offer-001二维数组中的查找
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
剑指offer JZ31 整数中1出现的次数 Python 解
-
剑指offer JZ54 字符流中第一个不重复的字符 Python 多解
-
剑指Offer积累-JZ1-二维数组中的查找
-
剑指offer之队列中的最大值(C++/Java双重实现)
-
剑指offer之在排序数组中查找数字 I(C++/Java双重实现)