目录
题目:剑指 Offer 51. 数组中的逆序对 - 力扣(Leetcode)
题目的接口:
解题思路:
代码:
过啦!!!
写在最后:
题目:剑指 Offer 51. 数组中的逆序对 - 力扣(Leetcode)
题目的接口:
class Solution {
public:
int reversePairs(vector<int>& nums) {
}
};
解题思路:
这一道题,我的思路是用双指针暴力求解,
但这个数组长度,O(N^2)的时间复杂度肯定是不可能把所有样例跑完,
看了大佬的思路,用的是归并排序,(如果不会归并排序,最好先去学一下)
我一开始看了很久没有搞明白为什么,
实际上,这个思路是利用的归并排序的一个特性,具体思路如下:
例: 数组 [ 7, 5, 2, 6, 0, 1, 5, 4 ]
我们就拿这个数组归并到最后一步的时候作为样例:
[ 2, 5, 6, 7 ] 和 [ 0, 1, 4, 5 ]
由于他们通过先前的归并已经是两个有序的数组,
而最后一步就两个数组每个元素比大小,然后尾插到临时数组上,最后再拷贝回来,
重点来了:
第一个数比大小 2 > 0 所以尾插 0 并让第二个数组的下标begin2++,
因为这两个是升序数组,2 > 0,也表明 2 之后的所有数都大于 0 ,
那么这里就有 4 ( mid + 1,也就是第一个数组的长度) 个逆序数对,
那么,当 2 和 4 比较,2 < 4 ,就尾插 2 进临时数组,让第一个数组下标begin1++,
这个时候,继续往下比较,5 > 4, 尾插 4 并让第二个数组的下标begin2++,
因为这两个是升序数组,5 > 4,也表明 5 之后的所有数都大于 4,
但是因为第一个数组已经是第二个数了,所以:
这里就有 3 ( mid + 1 - begin1 (也就是减去第一个数组的下标))个逆序数对。
综上所述,
我们只需要在第一个数组的值 > 第二个数组的值的时候,记录逆序数对 (mid + 1 - begin1) 即可。
下面是代码:
代码:
class Solution {
public:
//计数
int res = 0;
int reversePairs(vector<int>& nums) {
//创建临时数组
vector<int> tmp(nums.size());
//归并排序,我用的是我学的归并排序模板
merge_sort(nums, tmp, 0, nums.size() - 1);
return res;
}
private:
void merge_sort(vector<int>& nums, vector<int>& tmp, int begin, int end) {
if(begin >= end) return; //返回
//分治
int mid = (begin + end) >> 1;
merge_sort(nums, tmp, begin, mid);
merge_sort(nums, tmp, mid + 1, end);
//[begin][mid], [mid + 1][end]
//两个数组的下标
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
//临时数组的下标
int i = begin;
//比较大小之后尾插进临时数组
while(begin1 <= end1 && begin2 <= end2) {
if(nums[begin1] <= nums[begin2]) {
tmp[i++] = nums[begin1++];
}
else {
tmp[i++] = nums[begin2++];
//计算这一段的逆序数对数量//具体推导看文章的文字
res += mid + 1 - begin1; //整个思路的核心
}
}
//将没有插完的值全部尾插进临时数组
while(begin1 <= end1) tmp[i++] = nums[begin1++];
while(begin2 <= end2) tmp[i++] = nums[begin2++];
//将临时数组拷贝回原数组
for(int i = begin; i <= end; i++) {
nums[i] = tmp[i];
}
}
};
过啦!!!
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果喜欢本文的话,欢迎点赞和评论,写下你的见解。
如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。文章来源:https://www.toymoban.com/news/detail-410426.html
之后我还会输出更多高质量内容,欢迎收看文章来源地址https://www.toymoban.com/news/detail-410426.html
到了这里,关于【LeetCode】剑指 Offer(26)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!