2023/3/22美团面试
题目
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例2：
输入：[1，2，3，4，5，6，7，0]
输出：7
时间复杂度要求控制在o(n logn),所以不能用两个for循环进行比较。
最简单的方法——归并。
归并排序我之前只是搞懂了原理没有怎么去实现，搞得我遇到这道题直接抓瞎了，md气死我了！
请同学们一定要多写代码。好记性不如烂笔头。
排序部分
int mergesort(vector& nums, int left, int right, vector& tmp)
{
if (left >= right) return 0;
int mid = left (right - left) / 2;
int count = mergesort(nums, left, mid, tmp) mergesort(nums, mid 1, right, tmp);//mid 1-right;//left-mid
int i = left, j = mid 1, k = left;
for (k = left; k <= right; k )//至关重要，要更新tmp
{
tmp[k] = nums[k];
}
for (k = left; k <= right; k )
{
if (i == mid 1)
{
nums[k]=tmp[j ];
}
else if (j == right 1 || tmp[i] <= tmp[j])
{
nums[k]=tmp[i ];
}
else
{
nums[k] = tmp[j ];
count = (mid - i 1);
}
}
return count;
}
有的人喜欢搞两个函数，我觉得太麻烦了，这样子搞我更加直观。
原理图如下：
其实就是不断地二分，二分之后再二分知道编程一个元素一组，一个元素一组肯定是有序的呀，然后再两个两个比较，这里的两个两个是前后跨度为2的（如图所示），然后再四个四个比较（我就按双数来了，有可能是3，4个比较；4，5个比较，都可以，重在好理解！）然后再8，8个比较直到这个变成一个大组，这个大组都是有序的啦！
class solution {
public:
//2023/3/22美团面试
int mergesort(vector& nums, int left, int right, vector& tmp)
{
if (left >= right) return 0;
int mid = left (right - left) / 2;
int count = mergesort(nums, left, mid, tmp) mergesort(nums, mid 1, right, tmp);//mid 1-right;//left-mid
int i = left, j = mid 1, k = left;
for (k = left; k <= right; k )//至关重要，要更新tmp
{
tmp[k] = nums[k];
}
for (k = left; k <= right; k )
{
if (i == mid 1)
{
nums[k]=tmp[j ];
}
else if (j == right 1 || tmp[i] <= tmp[j])
{
nums[k]=tmp[i ];
}
else
{
nums[k] = tmp[j ];
count = (mid - i 1);
}
}
return count;
}
int reversepairs(vector& nums)
{
if (nums.size() < 2) return 0;
vector tmp(nums.size());
int c=mergesort(nums, 0, nums.size() - 1, tmp);
return c;
}
};
int main()
{
solution a;
vector nums = {
7,5,6,4 };
cout << a.reversepairs(nums) << endl;
for (auto i : nums)
{
cout << i << ' ';
}
cout << endl;
return 0;
}