剑指 Offer 51. 数组中的逆序对【力扣】
2021/10/17 23:12:15
本文主要是介绍剑指 Offer 51. 数组中的逆序对【力扣】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意理解
给定一个数组,计算逆序对的个数
问题分析
用归并
归并和逆序怎么关联?每次两个有序序列合并,对于左边的最小值放入最后序列的适合,最后序列左边的,比它小的,都是和逆序关系。问题转化为计算左边最小值放入最后序列时,右边序列已处理的元素个数。
其他
力扣
链接
class Solution { public: int mergeSort(vector<int>& nums, vector<int>& tmps, int l, int h) { if (l >= h) return 0; int mid = (l + h) / 2; int vert = mergeSort(nums, tmps, l, mid) + mergeSort(nums, tmps, mid+1, h); int i = l, j = mid + 1, pos = l; while(i <= mid && j <= h) { if (nums[i] <= nums[j]) { tmps[pos] = nums[i]; i++; vert += j - (mid+1); } else { tmps[pos] = nums[j]; j++; } pos++; } while(i <= mid) { tmps[pos] = nums[i]; pos++; i++; vert += j - (mid+1); } while(j <= h) { tmps[pos] = nums[j]; pos++; j++; } copy(tmps.begin()+ l, tmps.begin() + h + 1, nums.begin() + l); return vert; } int reversePairs(vector<int>& nums) { int len = nums.size(); vector<int> tmps(len); return mergeSort(nums, tmps, 0, len-1); } };
这篇关于剑指 Offer 51. 数组中的逆序对【力扣】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南