Eric's Blogs

Better Code, Better Life

0%

数组中的逆序对

发表于 分类于
本文字数： 5.6k 阅读时长 ≈ 5 分钟

题目描述

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

输入描述:

1
题目保证输入的数组中没有的相同的数字数据范围：	对于%50的数据,size<=10^4	对于%75的数据,size<=10^5	对于%100的数据,size<=2*10^5

示例1

输入

1
1,2,3,4,5,6,7,0

输出

1
7

解答

归并排序.leetcode上可以通过,牛客网剑指Offer没有完全通过,由于错误用例看不完整,正在排查原因

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int c = 0;

public int InversePairs(int[] array) {
    if (array == null || array.length <= 1) {
        return 0;
    }
    mergeSort(array);
    return c % 1000000007;
}

private int[] mergeSort(int[] n) {
    if (n.length <= 1) {
        return n;
    } else if (n.length == 2) {
        if (n[0] > n[1]) {
            c++;
            int t = n[0];
            n[0] = n[1];
            n[1] = t;
        }
        return n;
    }

    int[] n1, n2;
    n1 = mergeSort(Arrays.copyOfRange(n, 0, n.length / 2));
    n2 = mergeSort(Arrays.copyOfRange(n, n.length / 2, n.length));

    //todo merge 统计逆序对
    int[] n3 = new int[n.length];
    int i = 0, j = 0, k = 0;
    while (i < n1.length && j < n2.length) {
        if (n1[i] <= n2[j]) {
            n3[k] = n1[i];
            i++;
        } else {
            n3[k] = n2[j];
            j++;
            c += (n1.length - i);
        }
        k++;
    }
    for (; i < n1.length; k++, i++) {
        n3[k] = n1[i];
    }
    for (; j < n2.length; k++, j++) {
        n3[k] = n2[j];
    }
    return n3;
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5?answerType=1&f=discussion
来源：牛客网

题目描述：给定一个数组arr， 数组元素各不相同，求arr[i] > arr[j] 且 i < j的个数。

首先还是提出两个问题，带着问题来看题解，我觉得效率更好。
Q1：为什么归并排序需要额外的空间？
Q2：为什么此题的最优解法可以借助归并排序的思想？

方法一：暴力方法

对于此题，按住一个arr[i], 依次判断{i+1 … n-1]是否满足条件。n为数组的大小。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    const int kmod = 1000000007;
public:
    int InversePairs(vector<int> data) {
        int ret = 0;
        int n = data.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (data[i] > data[j]) {
                    ret += 1;
                    ret %= kmod;
                }
            }
        }

        return ret;
    }
};

对于10^5数据，O(N^2)算法显然超时。
时间复杂度：O(N^2)
空间复杂度：O(1)

方法二：归并排序思想

A1： 首先回答一下第一个问题，为什么归并排序需要额外空间？
显然我们知道，归并排序的过程就是，递归划分整个区间为基本相等的左右区间，之间左右区间各只有一个数字，然后就合并两个有序区间。
问题就出在了合并两个有序区间上，需要额外的空间。
为什么呢？
这里我举个例子，比如需要合并的两个有序区间为[3 4] 和 [1 2]
我们需要得到最后的结果为[1 2 3 4]， 如果不需要额外的空间的话，是做不到的，
当比较1 和 3 的时候， 1 比 3 小，就会覆盖原来的位置。

A2：回答第二个问题之前，先了解一下归并排序的过程，主要有以下两个操作：

  • 递归划分整个区间为基本相等的左右两个区间
  • 合并两个有序区间

可能看了代码，更好理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 合并过程
void merge__(vector<int> &arr, int l, int mid, int r) {
    // 在这个地方创建额外空间，是一种不好的做法，更好的做法，等下讲
    vector<int> tmp(r - l + 1);
    int i = l, j = mid + 1, k = 0;

    while (i <= mid && j <= r) {
        if (arr[i] >= arr[j]) {
            tmp[k++] = arr[j++];
        }
        else {
            tmp[k++] = arr[i++];
        }
    }

    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= r) {
        tmp[k++] = arr[j++];
    }

    for (k = 0, i = l; i <= r; ++i, ++k) {
        arr[i] = tmp[k];
    }
}

// 递归划分过程
void merge_sort__(vector<int> &arr, int l, int r) {
    // 只有一个数字，则停止划分
    if (l >= r) {
        return;
    }

    int mid = l + ((r - l) >> 1);
    merge_sort__(arr, l, mid);
    merge_sort__(arr, mid + 1, r);
    // 合并两个有序区间
    merge__(arr, l, mid, r);
}
// 要排序的数组 arr
void merge_sort(vector<int>& arr) {
    merge_sort__(arr, 0, arr.size() - 1);
}

明白了归并排序的过程，那么回答问题2.
如果两个区间为[4, 3] 和[1, 2]
那么逆序数为(4,1),(4,2),(3,1),(3,2)，同样的如果区间变为有序，比如[3,4] 和 [1,2]的结果是一样的，也就是说区间有序和无序结果是一样的。
但是如果区间有序会有什么好处吗？当然，如果区间有序，比如[3,4] 和 [1,2]
如果3 > 1, 显然3后面的所有数都是大于1， 这里为 4 > 1, 明白其中的奥秘了吧。所以我们可以在合并的时候利用这个规则。

直接上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
private:
    const int kmod = 1000000007;
public:
    int InversePairs(vector<int> data) {
        int ret = 0;
        merge_sort__(data, 0, data.size() - 1, ret);
        return ret;
    }


    void merge_sort__(vector<int> &arr, int l, int r, int &ret) {
        if (l >= r) {
            return;
        }

        int mid = l + ((r - l) >> 1);
        merge_sort__(arr, l, mid, ret);
        merge_sort__(arr, mid + 1, r, ret);
        merge__(arr, l, mid, r, ret);
    }

    void merge__(vector<int> &arr, int l, int mid, int r, int &ret) {
        vector<int> tmp(r - l + 1);
        int i = l, j = mid + 1, k = 0;

        while (i <= mid && j <= r) {
            if (arr[i] > arr[j]) {
                tmp[k++] = arr[j++];
                // 奥妙之处
                ret += (mid - i + 1);
                ret %= kmod;
            }
            else {
                tmp[k++] = arr[i++];
            }
        }

        while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        while (j <= r) {
            tmp[k++] = arr[j++];
        }

        for (k = 0, i = l; i <= r; ++i, ++k) {
            arr[i] = tmp[k];
        }
    }
};

刚才提到在函数内部开辟额外空间的做法很不好。因为这样会涉及到频繁的构建 vector 和析构vector，所以比较好的做法是：直接在最外层开辟一个足够大的数组，然后传引用到函数。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
private:
    const int kmod = 1000000007;
public:
    int InversePairs(vector<int> data) {
        int ret = 0;
        // 在最外层开辟数组
        vector<int> tmp(data.size());
        merge_sort__(data, tmp, 0, data.size() - 1, ret);
        return ret;
    }

    void merge_sort__(vector<int> &arr, vector<int> &tmp, int l, int r, int &ret) {
        if (l >= r) {
            return;
        }

        int mid = l + ((r - l) >> 1);
        merge_sort__(arr, tmp, l, mid, ret);
        merge_sort__(arr, tmp, mid + 1, r, ret);
        merge__(arr, tmp, l, mid, r, ret);
    }

    void merge__(vector<int> &arr, vector<int> &tmp, int l, int mid, int r, int &ret) {
        int i = l, j = mid + 1, k = 0;

        while (i <= mid && j <= r) {
            if (arr[i] > arr[j]) {
                tmp[k++] = arr[j++];
                ret += (mid - i + 1);
                ret %= kmod;
            }
            else {
                tmp[k++] = arr[i++];
            }
        }

        while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        while (j <= r) {
            tmp[k++] = arr[j++];
        }

        for (k = 0, i = l; i <= r; ++i, ++k) {
            arr[i] = tmp[k];
        }
    }

};

时间复杂度：O(NlogN)
空间复杂度：O(N)