剑指offer51. 逆序对 P249

剑指offer51. 逆序对 P249

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

归并的思想
const int MAX = 100000000; // 模值 如果答案比较大，可以根据题意返回取模结果
int mergeArray(int *nums, int *copy, int start, int end){
	if (start >= end) 
	    return 0;
	int mid = ((end - start) >> 1) + start;
	int left = mergeArray(nums, copy, start, mid); //先递归才能保证下面左右子数组有序
	int right = mergeArray(nums, copy, mid + 1, end);
	
	int count = 0;                        // 此次归并的逆序数
	int i = mid, j = end, index_copy = end;  // 从右到左遍历、对比
	
	while (i >= start && j > mid ) {    // 两段子数组都没有到头
// 因为两段都排续了，第一段最右边nums[i]的比第二段最右num[j]的大，
// 证明nums[i]比第二段剩下的所有（mid+1到j）都大，对于对应的逆序数就是第二段剩余的数字个数
		if (nums[i] > nums[j]) {   
			count += j - mid;                     // 第二段剩余个数
            for (int k = mid + 1; k <= j; ++k)         // 在这里可以输出所有逆序对
				printf("%d - %d, ", nums[i], nums[k]);
			copy[index_copy--] = nums[i--];  
		} else {
			copy[index_copy--] = nums[j--];
		}
		if (count > MAX) count %= MAX;    // 可选项，太大了的话就取给定的max模 
	}
	while (i >= start) copy[index_copy--] = nums[i--];  //有一段没有遍历完，加到copy
	while (j > mid)    copy[index_copy--] = nums[j--]; 
	for (int i = start; i <= end; ++i)
		nums[i] = copy[i];  
// 在递归里上一次操作的是copy，但是下次比较的是nums，所以要把更新的数组重给nums 
	return count + left + right;
}

int InversePairs(int *nums, int len) {
	if (nums == NULL || len < 2)  return 0;
	int *copy = new int[len];
	for (int i = 0;i < len; ++i)    copy[i] = nums[i];   // 复制辅助数组
	int ans = mergeArray(nums, copy, 0, len - 1); 
	delete[] copy;   return ans;    
}