当前位置: 首页> 文旅> 艺术 > 网页界面设计与制作书籍_杭州建设工程招标网新址_佛山网站建设维护_口碑营销成功案例

网页界面设计与制作书籍_杭州建设工程招标网新址_佛山网站建设维护_口碑营销成功案例

时间:2025/7/9 10:53:00来源:https://blog.csdn.net/weixin_65043441/article/details/142787466 浏览次数:0次
网页界面设计与制作书籍_杭州建设工程招标网新址_佛山网站建设维护_口碑营销成功案例

题目描述:

给定一个数组 nums ,如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

  1. 给定数组的长度不会超过50000
  2. 输入数组中的所有数字都在32位整数的表示范围内。

题目链接:

. - 力扣(LeetCode)

题目主要思路:

其实就是利用归并分治的思想,但是跟 “LCR170. 交易中的逆序队” 以及 "315. 计算右侧小于当前元素的个数" 这两道题目的结构不太一样。为什么?因为上述两道题,可以借助归并的时候顺便计算结构,即我们在判断nums[cur1] 和 nums[cur2]的时候可以顺便计算结果,而这道题的结果条件是nums[i] > 2*nums[j]。

这道题如果我们在判断nums[cur1] 和 nums[cur2]的时候顺便计算结果,很容易漏结果并且复杂些许。那为什么说利用归并分治的思想呢?因为我们可以在归并前计算结果。

解题代码:

class Solution {
public:int tmp[50010] = {0};int reversePairs(vector<int>& nums) {return mergeSort(nums, 0, nums.size()-1);}int mergeSort(vector<int>& nums, int left, int right){if (left >= right) return 0;int mid = (left + right) >> 1;int ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid+1, right);int cur1 = left, cur2 = mid+1, i = 0;// 先计算结果while (cur1 <= mid) {while (cur2 <= right && nums[cur1]/2.0 <=nums[cur2]) ++cur2;if (cur2 > right) break;ret += right - cur2 + 1;++cur1;}cur1 = left, cur2 = mid+1;while (cur1 <= mid && cur2 <= right){   // 排降序 if (nums[cur1] < nums[cur2]) {tmp[i++] = nums[cur2++];}else {tmp[i++] = nums[cur1++];}}while (cur1 <= mid) {tmp[i++] = nums[cur1++];}while (cur2 <= right) {tmp[i++] = nums[cur2++];}// 将排序完的数据写入原数组for (int i = left; i <= right; ++i) {nums[i] = tmp[i-left];}return ret;}
};

关键字:网页界面设计与制作书籍_杭州建设工程招标网新址_佛山网站建设维护_口碑营销成功案例

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: