ToB企服应用市场:ToB评测及商务社交产业平台

标题: LeetCode/数组中的逆序对 [打印本页]

作者: 王國慶 时间: 2022-6-24 13:35
标题: LeetCode/数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

最简单的思路就是二重循环暴力匹配
更优的方法是通过归并递归，先拆分成子问题，先计算区间内的逆序数，然后归并，同时计算区间之间的逆序数，并把总数加起来
计算两区间之间的逆序对时，可以跟合并区间操作统一起来，在归并合并区间时，我们使用了两个指针记录两区间初始位置
相互比较大小，复制给辅助数组，并轮流前进，以从前往后的方向为例，当右指针指向数小于左指针，那么它也必然小于左指针之后的数
直接计算得到了这个数相对左区间的逆序对，这是就利用了归并区间内有序的性质和区间相对位置确定的性质

[code]class Solution {public: int reversePairs(vector& nums) { vector tmp(nums.size()); return mergeSort(0, nums.size() - 1, nums, tmp);//归并排序 }private: int mergeSort(int l, int r, vector& nums, vector& tmp) { // 终止条件 if (l >= r) return 0;//逆序数返回0 // 递归划分 int m = (l + r) / 2; int res = mergeSort(l, m, nums, tmp) + mergeSort(m + 1, r, nums, tmp);//计算各自区间内的逆序对并排序 // 合并阶段，计算两区间之间的逆序对 int i = l, j = m + 1;//记录左右区间首指针 for (int k = l; k

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)