1 /************************************************************************* 2     > File Name: 34_InversePairsInArray.c 3     > Author: Juntaran 4     > Mail: JuntaranMail@gmail.com 5     > Created Time: 2016年09月02日 星期五 20时05分05秒 6  ************************************************************************/ 7  8 #include <stdio.h> 9 #include <malloc.h>10 11 int InversePairsCore(int* nums, int* copy, int left, int right)12 {13     if (left == right)14     {15         copy[left] = copy[right];16         return 0;17     }18     int newlength = (right - left) / 2;19     20     // 递归21     int leftCount  = InversePairsCore(copy, nums, left, left+newlength);22     int rightCount = InversePairsCore(copy, nums, left+newlength+1, right);23     24     // i初始化为前半段最后一个数字下标25     int i = left + newlength;26     // j初始化为后半段最后一个数字下标27     int j = right;28     29     int indexCopy = right;30     int count = 0;31     32     while (i>=left && j>=left+newlength+1)33     {34         if (nums[i] > nums[j])35         {36             copy[indexCopy--] = nums[i--];37             count += j - left - newlength;38         }39         else40         {41             copy[indexCopy--] = nums[j--];42         }43     }44     45     for (i; i >= left; --i)46         copy[indexCopy--] = nums[i];47     for (j; j>=left+newlength+1; --j)48         copy[indexCopy--] = nums[j];49     50     return leftCount + rightCount + count;51 }52 53 int InversePairs(int* nums, int length)54 {55     if (nums==NULL || length<=0)56         return -1;57     58     int* copy = (int*)malloc(sizeof(int)*length);59     for (int i = 0; i < length; ++i)60         copy[i] = nums[i];61     62     int count = InversePairsCore(nums, copy, 0, length-1);63     delete[] copy;64     65     return count;66 }67 68 int main()69 {70     int nums[] = {7,5,6,4};71     int length = 4;72     int ret = InversePairs(nums, length);73     printf("%d\n", ret);74 }