做gif图的网站,建网站 pdf,黄骅港船舶动态计划表,2017网站开发发展前景❓剑指 Offer 51. 数组中的逆序对
难度#xff1a;困难
在数组中的两个数字#xff0c;如果前面一个数字大于后面的数字#xff0c;则这两个数字组成一个逆序对。输入一个数组#xff0c;求出这个数组中的逆序对的总数。
示例 1: 输入: [7,5,6,4] 输出: 5 限制#xff…❓剑指 Offer 51. 数组中的逆序对
难度困难
在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组求出这个数组中的逆序对的总数。
示例 1: 输入: [7,5,6,4] 输出: 5 限制
0 数组长度 50000
思路归并排序
预备知识
「归并排序」是用分治思想分治模式在每一层递归上有三个步骤
分解Divide将 n 个元素分成个含 n/2 个元素的子序列。解决Conquer用 合并排序法 对两个子序列递归的排序。合并Combine合并两个已排序的子序列已得到排序结果。 具体的我们以一组无序数列141215131116为例分解说明如下图所示 在待排序序列长度为 1 的时候递归开始「回升」因为我们默认长度为 1 的序列是排好序的。
具体思路 那么求逆序对和归并排序又有什么关系呢关键就在于「归并」当中「并」的过程。 合并阶段 本质上是 合并两个排序数组 的过程
每当遇到 左子数组当前元素 右子数组当前元素 时意味着 「左子数组当前元素i 至 末尾元素m」 与 「右子数组当前元素」 构成了若干 「逆序对」 ;逆序对数 cnts (m - i 1) 。 考虑在归并排序的合并阶段统计「逆序对」数量完成归并排序时也随之完成所有逆序对的统计。
代码(C、Java)
C
class Solution {
private:int cnts 0;void mergeSort(vectorint nums, vectorint tmp, int l, int h){if(h - l 1) return;//分解int m l (h - l) / 2;mergeSort(nums, tmp, l, m);mergeSort(nums, tmp, m 1, h);//解决 合并int k l, i l, j m 1;while(i m || j h){if(i m) tmp[k] nums[j];else if(j h || nums[i] nums[j]) tmp[k] nums[i];else{//此时i~m对应数组中的数都比nums[j]大tmp[k] nums[j];cnts (m - i 1);} }for(k l; k h; k){nums[k] tmp[k];}}
public:int reversePairs(vectorint nums) {vectorint tmp(nums.size());//辅助数组临时记录中间合并的子数组mergeSort(nums, tmp, 0, nums.size() - 1);return cnts;}
};Java
class Solution {private int cnts 0;private void mergeSort(int[] nums, int[] tmp, int l, int h){if(h - l 1) return;//分解int m l (h - l) / 2;mergeSort(nums, tmp, l, m);mergeSort(nums, tmp, m 1, h);//解决 合并int k l, i l, j m 1;while(i m || j h){if(i m) tmp[k] nums[j];else if(j h || nums[i] nums[j]) tmp[k] nums[i];else{//此时i~m对应数组中的数都比nums[j]大tmp[k] nums[j];cnts (m - i 1);} }for(k l; k h; k){nums[k] tmp[k];}}public int reversePairs(int[] nums) {int[] tmp new int[nums.length];//辅助数组临时记录中间合并的子数组mergeSort(nums, tmp, 0, nums.length - 1);return cnts;}
}运行结果 复杂度分析
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)其中 n 为数组的长度同归并排序 O ( n l o g n ) O(nlogn) O(nlogn)。空间复杂度 O ( n ) O(n) O(n)归并排序需要用到一个临时数组。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
