题目描述
在数组中的两个数字如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数。
样例
输入:[1,2,3,4,5,6,0]
输出:6
参考:https://www.bilibili.com/video/BV1Hv41167ft?from=search&seid=2747792850762973218
归并排序的典型应用 思路: 如果是从小到大的有序数组,是不存在逆序对的,产生逆序对的一定是无序或者递减的 无序变有序的过程就是将逆序对的两个元素进行交换,从而消灭逆序对 所以把交换的次数数出来,就是逆序对的个数 最简单的是冒泡(冒泡排序会进行逆序对的交换),但是时间复杂度高 用归并来实现排序。 在基础归并上加了一个句30行的:count+=(mid-i+1) 也就是左边子列的i大于右边子列j时候,由于左边是递增排序的,说明左边i之后的数字都大于j 所以逆序对就是左边子列i之后的元素的个数,就是mid-i+1 class Solution { public: void merge(vector<int>& nums,int left,int right){ if(left>=right) return; int mid=left+(right-left)/2; merge(nums,left,mid); merge(nums,mid+1,right); sort2vector(nums,left,mid,right); //left是左边子列开头,mid是左边子列结尾;mid+1是右边子列开头,right是右边子列结尾 } void sort2vector(vector<int>& nums,int left,int mid,int right){ int i=left,j=mid+1; int len=right-left+1; while(i<=mid&&j<=right){ if(nums[i]<=nums[j]) ans.push_back(nums[i++]); else{ count+=(mid-i+1);//对于[5 7] [4 6] 5>4,所以左边都大于4,count+2; ans.push_back(nums[j++]); } } while(i<=mid) ans.push_back(nums[i++]); while(j<=right) ans.push_back(nums[j++]); for(int i=0;i<len;i++) nums[i+left]=ans[i];//ans是从0开始,但是nums从left开始 ans.clear(); } int reversePairs(vector<int>& nums) { merge(nums,0,nums.size()-1); return count; } private: int count=0; vector<int> ans; //把暂存的vector定义外面,每次用完clear,用时会少 };