• 数组中的逆序对
    • 题目
    • 解题思路

    数组中的逆序对

    题目

    牛客网

    在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

    输入描述: 题目保证输入的数组中没有的相同的数字

    数据范围：

    1.     对于%50的数据,size<=10^4
    3.     对于%75的数据,size<=10^5
    5.     对于%100的数据,size<=2*10^5

    解题思路

    1. 1. 使用归并排序的方式，划分子数组
    2. 2. 两个子数组进行对比，有两个分别指向两个数组末尾的指针 `f,s`，数组分割下标为 `mid`，如果 `array[f] > array[s]`那么，就有`s - mid`个 `array[f]` 的逆序
    3. 3. 依此类推，最终将数组排序，并且获得结果
    1. public int InversePairs(int[] array) {
    2. long[] sum = {0};
    3. if (array == null || array.length == 0) {
    4.         return (int) sum[0];
    5. }
    7. int[] temp = new int[array.length];
    8. mergeSort(array, 0, array.length - 1, temp, sum);
    9. return (int) (sum[0] % 1000000007);
    10. }
    13. private void mergeSort(int[] array, int start, int end, int[] temp, long[] sum) {
    14. if (start == end) {
    15.         return;
    16. }
    18. int mid = (start + end) / 2;
    20. mergeSort(array, start, mid, temp, sum);
    21. mergeSort(array, mid + 1, end, temp, sum);
    23. int f = mid, s = end;
    24. int t = end;
    25. while (f >= start && s >= mid + 1) {
    26.         if (array[f] > array[s]) {
    27.                 temp[t--] = array[f--];
    28.                 sum[0] += s - mid;
    29.         } else {
    30.                 temp[t--] = array[s--];
    31.         }
    32. }
    34. while (f >= start) {
    35.         temp[t--] = array[f--];
    36. }
    38. while (s >= mid + 1) {
    39.         temp[t--] = array[s--];
    40. }
    42. for (int i = end, j = end; i >= start; ) {
    43.         array[j--] = temp[i--];
    44. }
    45. }