题解 | #数组中的逆序对#

如何用分治思想统计数组中的逆序对？

分治是将较大的问题规模分解成相同结构的规模较小的子问题，再合并子问题的解。此题可以利用归并排序的思想，将原始数组分割成由较小元素的子数组，并统计每个子数组中的逆序对，再统计合并后的数组的逆序对，而分割的两个数组是有序的，在合并时，前面一个数组的某个元素如果大于后面数组的某个元素，那么前面的数组该元素后面的数组都会大于后面数组的那个元素，此时就可以一次性统计这些元素为逆序对。

参考

https://blog.nowcoder.net/n/64be4788b4e442599d5b532f52feb2dc?f=comment

https://blog.nowcoder.net/n/55c9f7f11fb04ab29b38d4430a766912?f=comment

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param data int整型一维数组 
 * @return int整型
 */
export function InversePairs(data: number[]): number {
    // write code here
    const mergeSort = (nums: number[], startIndex: number, endIndex: number): number => {
        let count = 0; // 统计当前层的逆序对
        if (startIndex >= endIndex) {
            return count;
        }

        let middleIndex = Math.floor((startIndex+endIndex)/2);
        count = mergeSort(nums, startIndex, middleIndex) + mergeSort(nums, middleIndex+1, endIndex);  // 获得两个子数组中的逆序对 

        const tempArr: number[] = new Array(endIndex-startIndex+1);  // 用于将当前层的两个分割后排序的数组合并成一个整体有序的数组
        let firstIndex = startIndex;  // 用于遍历第一个分割的数组
        let secondIndex = middleIndex+1;  // 用于遍历第二个分割的数组
        let tempIndex = 0;  // 用于遍历临时排序的数组
        // 归并排序
        while (firstIndex <= middleIndex && secondIndex <= endIndex) {
            if (nums[firstIndex] < nums[secondIndex]) {  // 此时不是逆序对
                tempArr[tempIndex++] = nums[firstIndex++];
            }
            else {  // 此时是逆序对，由于两个分割的数组有序，此时firstIndex后面的元素都大于secondIndex对应的元素，一起统计
                count += (middleIndex-firstIndex+1);
                tempArr[tempIndex++] = nums[secondIndex++];
            }
        }

        // 将剩余的元素排序
        while (firstIndex <= middleIndex) {  // 第一个数组还剩下元素，第二个数组没有元素了，此时逆序对已经统计完了（因为没有第二个数组元素比较了）
            tempArr[tempIndex++] = nums[firstIndex++];
        }
        while (secondIndex <= endIndex) {  // 第二个数组还剩下元素，第一个数组没有元素了，同理此时的逆序对也已经统计完了
            tempArr[tempIndex++] = nums[secondIndex++];
        }
        // 将temp中有序的元素放到原数组中对应位置，使原数组有序
        for (let k = 0; k < tempArr.length; ++k) {
            nums[k+startIndex] = tempArr[k];
        }

        return count%1000000007;
    }

    return mergeSort(data, 0, data.length-1);
}

public class Solution {
    public int InversePairs(int [] array) {
        // 逆序对是两个数字，将数组分成两半，左半边元素分别和右半边元素比较看看是否是逆序，归并做法
        return mergeSort(array, 0, array.length-1);
    }

    private int mergeSort(int[] array, int left, int right) {  // left和right是闭区间
        int count = 0;  // 统计当前层的逆序对
        if (left >= right) {
            return count;
        }

        int middle = (int)Math.floor((left+right)/2);
        count = mergeSort(array, left, middle) + mergeSort(array, middle+1, right);  // 统计两半数组的逆序数总和
        count = count % 1000000007;  // Java还需要在这里取模，防止溢出

        int[] tempArray = new int[right-left+1];  // 当前层的临时排序数组
        int tempIndex = 0;
        int firstIndex = left;  // 遍历左半部分数组
        int secondIndex = middle+1;  // 遍历右半部分数组

        while (firstIndex <= middle && secondIndex <= right) {
            if (array[firstIndex] < array[secondIndex]) {
                // 此时不是逆序对
                tempArray[tempIndex++] = array[firstIndex++];
            }
            else if (array[firstIndex] >= array[secondIndex]) {
                // 此时是逆序对，并且firstIndex及后面的元素都可以和secondIndex组成逆序对
                count += (middle - firstIndex + 1);
                tempArray[tempIndex++] = array[secondIndex++];
            }
        }

        // 左半数组和右半数组只有任意一边有元素，都不会组成逆序对了，只需进行排序就行
        while (firstIndex <= middle) {
            tempArray[tempIndex++] = array[firstIndex++];
        }
        while (secondIndex <= right) {
            tempArray[tempIndex++] = array[secondIndex++];
        }

        // 将排序好的部分放到原数组中
        for (int k = 0; k < tempArray.length; ++k) {
            array[left+k] = tempArray[k];
        }

        return count % 1000000007;
    }
}