【面试题036】数组中的逆序对

【面试题036】数组中的逆序对

题目：

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

输入一个数组，求出这个数组中的逆序对的总数。

思路一：

遍历扫描整个数组，没扫描到一个数字的时候，逐个比较这个数字和它后面的数字的大小。

如果后面的数字比它小，则这两个数字就组成了一个逆序对。

——算法的时间复杂度是O(n)。

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

#include <iostream>

using namespace std;

int InversePairs(int *data, int length)
{
    int count = 0;
    for (int i = 0; i < length - 1; ++i)
    {
        for (int j = i + 1; j < length; ++j)
        {
            if (data[i] > data[j])
            {
                count++;
            }
        }
    }
    return count;
}

int main()
{
    int data[] = {7, 5, 6, 4};
    int length = sizeof(data) / sizeof(data[0]);
    cout << InversePairs(data, length) << endl;
    return 0;
}

思路二：

可以考虑先比较相邻的两个数字的情况。

把长度为4的数组分成两个长度为2的子数组，再把这两个子数组分别拆分成两个长度为1的子数组。

接下来一边合并相邻的子数组，一边统计逆序对的数目。

{7} {5} 这两个长度为1的子数组合并的时候，因为7 > 5所以，它们合并的时候会构成一个逆序对，

所以应该对这两对子数组排序，以免在以后的统计过程中在重复统计。

每次一个指针指向子数组的最后一个元素，合并两个子数组的时候，利用最后一个元素的指针做比较，

并且向前移动，——合并的这两个数组移动到第三个数组当中，

每次比较的时候把较大的数字从后到前移动到一个辅助数组当中，注意辅助数组的指针在放入较大元素后，

要左移一位。之所以这么做是为了保证辅助数组中的数字都是有序的。

先统计子数组内部的逆序数。
然后在统计相邻子数组的逆序数。
在统计的过程中还要对相邻子数组进行排序。

归并的时间复杂度是O(nlogn)，比最直观的O(n^2)要快，但同时归并排序需要一个长度为n的辅助空间。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#include <iostream>

using namespace std;

int InversePairsCore(int *data, int *copy, int start, int end)
{
    if(start == end)
    {
        copy[start] = data[start];
        return 0;
    }

    int length = (end - start) / 2;

    //copy 和 data的顺序为什么要交互啊
    int left = InversePairsCore(copy, data, start, start + length);
    int right = InversePairsCore(copy, data, start + length + 1, end);

    // i初始化为前半段最后一个数字的下标
    int i = start + length;
    // j初始化为后半段最后一个数字的下标
    int j = end;
    int indexCopy = end;
    int count = 0;
    while(i >= start && j >= start + length + 1)
    {
        if(data[i] > data[j])
        {
            copy[indexCopy--] = data[i--];
            count += j - start - length;
        }
        else
        {
            copy[indexCopy--] = data[j--];
        }
    }

    for(; i >= start; --i)
        copy[indexCopy--] = data[i];

    for(; j >= start + length + 1; --j)
        copy[indexCopy--] = data[j];

    return left + right + count;
}

int InversePairs(int *data, int length)
{
    if (data == NULL || length < 0)
    {
        return 0;
    }
    int *copy = new int[length];
    for(int i = 0; i < length; ++i)
    {
        copy[i] = data[i];
    }

    int count = InversePairsCore(data, copy, 0, length - 1);
    delete[] copy;

    return count;
}

int main()
{
    int data[] = {7, 5, 6, 4};
    int length = sizeof(data) / sizeof(data[0]);
    cout << InversePairs(data, length) << endl;
    return 0;
}