剑指offer之找出数组中的逆序对 - 如风 - CSDN博客
剑指offer之找出数组中的逆序对
& & & & &在数组中的俩个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组的逆序对的总数。
& & 看到这个问题时，我先想到的方法是遍历整个数组，扫描到一个数字，逐个比较它后面的数字大小。如果后面的数字比它小，则这两个数字就组成一个逆序对，这种方法的是假复杂度是O（N*N），显然，我们必须找到更加高效的算法。
& & & & 想想其实可以使用排序来解决这个问题，每次数组里的数据发生一次交换，就说明有一对逆序对，我们可以选择的排序有快速排序和堆排序，这两种排序的时间效率都是比较高的都是O（lgN）。
& & & & & 但是，还有一中排序和找逆序 对的思想一致，那就是归并排序。归并排序就是把一个数组分成前半段和后半段，然后又拆分前半段为两段，后半段为两段。。。这样拆分下去，最后的子数组长度会为1，开始归并，每一次归并两个数组的时候，如果左数组比右数组大，那么着就是一个逆序。记录所有左数组比右数组大的情况，就是全部的逆序数目。
&pre name=&code& class=&cpp&&int InversePairsCore(int* data, int* copy, int start, int end)
if (start == end)
copy[start] = data[start];
int length = (end-start)/2;
int left = InversePairsCore(copy, data, start, start+length);
int right = InversePairsCore(copy, data, start+length+1, end);
int i = start+ //前半段最后一个数字的下标
int indexCopy =
int count = 0;
while (i&=start && j&=start+length+1) {
if (data[i] & data[j]) {
copy[indexCopy--] = data[i--];
count += j-start-
copy[indexCopy--] = data[j--];
for (; i&= --i)
copy[indexCopy--] = data[i];
for (; j&=start+length+1; --j)&pre name=&code& class=&cpp&&
copy[indexCopy--] = data[j];
return left+right+
int InversePairs (int* data, int length)
if (data == NULL || length & 0)
int *copy = new int[length];
for (int i=0; i&++i)
copy[i]=data[i];
int count=InversePairCore(data,copy,0,length);
我的热门文章
即使是一小步也想与你分享基础算法（51）
# @left part: [start, mid]
# @right part: (mid, end]
def merge(data, start, mid, end):
if mid & start or end & mid:
reverse = 0
'''
@ for start, it play as the start index of left part, and mid
@ play as the en
@ mid + 1 (st2) play as the start index of right part, and end
@ play as the end index of right part.
'''
#@ start of right part
st2 = mid + 1
while start &= mid and st2 &= end:
if data[start] & data[st2]:
# move data[st2] to start, and data[start, - 1]
# move back by 1
data.insert(start, data.pop(st2))
reverse += st2 - start
# [start, mid] move back by one, so start = start + 1
# and mid = mid + 1
start += 1
# same as start & mid, move back by 1
# no insert or move, so start = start + 1
start += 1
return reverse
def mergeSortWithCount(data, start, end):
#just one item or Node, return dirctly
if len(data) &= 1 or end &= start:
mid = (start + end) && 1
#@ reversepair number of left part
left = mergeSortWithCount(data, start, mid)
# reversepair number of right part
right = mergeSortWithCount(data, mid + 1, end)
# toal count of reverse pair = left + right + {merger(left, right)}
return merge(data, start, mid, end) + left + right
这个题，还可以通过线段树来实现，有兴趣的可以找一些线段树的题练一练。下面的链接是我学习线段树的第一个博客。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：152370次
积分：3936
积分：3936
排名：第7708名
原创：244篇
评论：10条
(1)(1)(50)(33)(42)(5)(1)(56)(43)(2)(2)(9)剑指offer（42）
　　题目描述：
　　输入一个数组，求出其中逆序对的总个数
　　示例：
　　输入：{7， 5， 6， 4} ，逆序对有{7,6}，{7,5}，{7,4}，{5,4}，{6,4}几种情况
　　因此输出5　　
　　分析：
　　利用归并排序的思想进行排序，时间复杂度O(nlgn）
　　代码：　　
int inversePairsCore(vector&int&& nums,vector&int&& copy,int begin,int end){
if(begin&=end){
copy[begin]=nums[begin];
int mid=begin+(end-begin)/2;
int left=inversePairsCore(copy,nums,begin,mid);
int right=inversePairsCore(copy,nums,mid+1,end);
int i=mid,j=
int index=
int count=0;
while(i&=begin&&j&mid){
if(nums[i]&nums[j]){
copy[index--]=nums[i--];
count+=(j-mid);
copy[index--]=nums[j--];
while(i&=begin) copy[index--]=nums[i--];
while(j&mid)
copy[index--]=nums[j--];
return left+right+
int inversePairs(vector&int&& nums){
if(nums.size()&=1)
vector&int& copy(nums.begin(),nums.end());
return inversePairsCore(nums,copy,0,nums.size()-1);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：77937次
积分：2042
积分：2042
排名：第18272名
原创：119篇
转载：21篇
评论：10条
(2)(4)(20)(63)(12)(4)(1)(5)(3)(9)(11)(2)(2)(3)(4)剑指offer面试题36-数组中的逆序对 -
爱橙子的OK绷的专栏 - CSDN博客
剑指offer面试题36-数组中的逆序对
问题描述：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
例如， 在数组{7,5,6,4}中，一共存在5个逆序对，分别是(7,6),(7,5),(7,4),(6,4)和(5,4)，输出5.
问题求解：归并排序
以数组｛7, 5, 6, 4｝为例来分析统计逆序对的过程。每次扫描到一个数字的时候，我们不能拿它和后面的每一个数字作比较，否则时间复杂度就是O(n^2)，因此我们可以考虑先比较两个相邻的数字。
如图5.1 (a)和图5.1 (b)所示，先把数组分解成两个长度为2的子数组， 再把这两个子数组分别拆分成两个长度为1的子数组。接下来一边合并相邻的子数组， 一边统计逆序对的数目。在第一对长度为1 的子数组{7}、{5}中7大于5 ，因此(7, 5)组成一个逆序对。同样在第二对长度为1 的子数组{6}、{4}中也有逆序对(6, 4)。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组排序(图5.1 (c)所示)，以免在以后的统计过程中再重复统计。
如图所示，声明p1,p2,p3三个指针，分别为左半段下标，右半段下标，以及辅助数组下标。从后往前依次遍历左半段和右半段：
(a) P1指向的数字大于P2指向的数字，表明数组中存在逆序对. P2指向的数字是第二个子数组的第二个数字，因此第二个子数组中有两个数字比7小.
把逆序对数目加2，并把7 复制到辅助数组，向前移动P1和P3.
(b) P1指向的数字小子P2指向的数字，没有逆序对. 把P2指向的数字复制到辅助数组，并向前移动P2和P3.
(c) P1指向的数字大于P2指向的数字，因此存在逆序对.
由于P2指向的数字是第二个子数组的第一个数字，子数组中只有一个数字比5小.
把逆序对数目加1，并把5复制到辅助数组，向前移动P1和P3 .
总结出统计逆序对的过程：先把数组分隔成子数组， 先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。我们不难发现这个排序的过程实际上就是归并排序。
class Solution {
int InversePairs(vector&int& data) {
= data.size();
return mergeSort(data, 0, n-1);
int mergeSort(vector&int&& data, int start, int end) {
if(start &= end) return 0;
int mid = start + (end-start) / 2;
int lcnt = mergeSort(data, start, mid);
int rcnt = mergeSort(data, mid+1, end);
vector&int& copy(data);
int cnt = 0;
int idxCopy =
while(i&=start && j &= mid+1)
if(data[i] & data[j])
copy[idxCopy--] = data[i--];
cnt += j -
copy[idxCopy--] = data[j--];
while(i &= start) {
copy[idxCopy--] = data[i--];
while(j &= mid+1) {
copy[idxCopy--] = data[j--];
for(int i= i&= i++) {
data[i] = copy[i];
return (lcnt+rcnt+cnt);
参考剑指offer
我的热门文章
即使是一小步也想与你分享