剑指offer之面试题36数组中的逆序对

矫情吗；* 2022-07-24 04:04 107阅读 0赞

**问题描述**：

在数组中的两个数字如果前面的一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

**实现代码**如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <limits.h>
    
    int doFindInverseCount(int *date,int *copy,int left,int right){
    	if(left==right){
    		copy[left]=date[left];
    		return 0;
    	}
    	int len = (right-left)/2;
    	int leftcount = doFindInverseCount(date,copy,left,left+len);
    	int rightcount = doFindInverseCount(date,copy,left+len+1,right);
    	int leftPosition=left+len;
    	int rightPosition=right;
    	int indexCopy = right;
    	int count = 0;
    	
    	while(leftPosition>=left && rightPosition>=left+len+1){
    		if(date[leftPosition]>date[rightPosition]){
    			copy[indexCopy--]=date[leftPosition--];
    			count+=rightPosition-left-len;
    		}else{
    			copy[indexCopy--]=date[rightPosition--];
    		}
    	}
    	for(;leftPosition>=left;leftPosition--){
    		copy[indexCopy--]=date[leftPosition--];
    	}
    	for(;rightPosition>=left+len+1;rightPosition--){
    		copy[indexCopy--]=date[rightPosition--];
    	}
    	int i;
    	
    	for(i=left;i<=right;i++){
    		date[i]=copy[i];
    	}
    	
    	return leftcount + count + rightcount;
    }
    int findInverseCount(int *date,int len){
    	if(date==NULL || len <=0)return 0;
    	int *copy  = (int *)malloc(sizeof(int)*len);
    	int count = doFindInverseCount(date,copy,0,len-1);
    	return count;
    }
    int main(int argc, char *argv[])
    {
    	int date[]={
    		7,5,6,4
    	};
    	int len=  sizeof(date)/sizeof(int);
    	
    	int rs = findInverseCount(date,len);
    	printf("%d\n",rs);
    	return 0;
    }

上面算法的时间复杂度是O(nlgn)，空间复杂度是O(n)。

所以上面是用空间换时间的算法。

**参考资料**：  
剑指offer  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51383887  
作者：WSYW126