【剑指offer】51 - 数组中的逆序对

题目描述

• 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。例如，在{7,5,6,4}中，一共存在 5 个逆序对，分别是（7,6）、（7,5）、（7,4）、（6,4）和（5,4）；

解题思路

• 本题最直接的解决方法是：遍历数组，每扫描一个数字，逐个比较它与后面数字的大小，若大于后面数字，则组成一个逆序对。这个算法类似于冒泡排序的实现，在冒泡排序过程中每交换一次，则逆序对的个数++，时间复杂度为O(n2)
• 我们换一个角度考虑，如果那当前元素和后面的每个元素进行比较的话，则时间复杂度为O(n2)，为了降低时间复杂度，这种比较方法是不可行的。

• 既然不能和后面所有的元素进行比较，那么我们是否可以考虑让当前遍历到的元素与和它相的元素不进行比较呢？为了达到这个目的，我们需要递归对数组进行分解，一直递归到最深层次，即一个区间只有一个元素，此时我们可以边统计逆序对的个数，边对数组进行排序，我们举例说明：

  • 以{7 ，5， 6，4}为例，通过递归到最深层次，将数组分解为长度为以一的子数组
  • {7}，{5}，{6}，{4}；7 > 5，count+1；6 > 4，count + 1
  • 将数组进行排序合并，统计长度为 2 的子数组的逆序对的个数
  • {5 ，7}，{4，6}；我们需要两个指针分别 p1，p2 分别指向区间末尾，若 *p1 > *p2，则说明第二个区间中两个数都比 *p1 小，此时 count+=2，将 7 压入排序数组，p1–；此时 *p1 < *p2，无逆序对，将 6 压入排序数组，*p2–；此时 *p1 > *p2，说明存在逆序对，count+=1，将 5 压入排序数组中；
  • 上述过程：分别用两个指针指向子数组的末尾，并每次比较两个指针指向的数字。若第一个大于第二个，则说明存在逆序对，对数即为第二个子区间元素的个数，若小于等于，则不构成逆序对。每次比较的时候把较大的数字从后向前复制到辅助数组中，确保数组元素递增。在把较大的数字复制到辅助数组中后，把对应的指针向前移动一位，进行下一轮
  • 在进行下一轮之前，我们需要将排好序的子数组内容拷贝回原数组

• 通过上面的例子，我们已经理解了这种算法的实现过程，这样我们统计逆序对个数的过程即为：先把数组分隔成子数组，统计出子数组内部的逆序对的数目，然后在统计出两个相邻子数组之间的逆序对的数目。统计过程中，需要对数组进行排序

• 我们上述的思路二和我们归并排序的算法一致，时间复杂度为 O(nlogn)，但是归并排序是一种以空间换时间的算法，排序过程中需要一个长度为 n 的数组

代码实现

• 基于冒泡排序算法的实现，时间复杂度为O(n2)

#include <iostream>
#include <vector>
using namespace std;

int InversePairs(vector<int> A, int n)
{
    //处理无效输入
    if(A.size() == 0 || n < 0)
        return 0;
    int count = 0;
    for(int i = 0 ; i < n; ++i)
    {
        for(int j = 0; j < n - i - 1; ++j)
        {
            if(A[j] > A[j + 1])
            {
                swap(A[j], A[j + 1]);
                count++;
            }
        }
    }
    return count;
}

int main()
{
    int arr[] = {1,2,3,4,5,6,7,8,9,0};
    vector<int> v(arr, arr + sizeof(arr)/sizeof(arr[0]));
    int count = InversePairs(v, sizeof(arr)/sizeof(arr[0]));
    cout << count << endl;
    return 0；
}

• 基于归并排序算法的实现，时间复杂度为O(nlogn)，空间复杂度为O(n)

#include <iostream>
#include <vector>
using namespace std;

int InversePairsCore(vector<int>& A, vector<int>& tmp, int begin, int end)
{
    if (begin == end)
    {
        tmp[begin] = A[begin];
        return 0;
    }
    //区间长度
    int len = (end - begin)/2;

    int left = InversePairsCore(A, tmp, begin, begin + len);
    int right = InversePairsCore(A, tmp, begin + len + 1, end);

    //i,j分别为左右子区间最后一个数字的下标
    int i = begin + len ;
    int j = end;

    //index为辅助数组最后一个数字的下标
    int index = end;
    int count = 0;
    while (i >= begin && j >= begin + len + 1)
    {
        if (A[i] > A[j])
        {
            //此种情况说明存在逆序对，逆序对的个数为右区间元素的个数
            tmp[index--] = A[i--];
            count += j - begin - len;
        }
        else
        {
            tmp[index--] = A[j--];
        }
    }

    //将子区间中剩余元素插入到辅助数组中
    for (; i >= begin; --i)
    {
        tmp[index--] = A[i];
    }

    for (; j >= begin + len + 1; --j)
    {
        tmp[index--] = A[j];
    }

    //将临时数组的值拷贝回原数组,则原数组的内容为当前排好序的子区间
    for (int i = end; i > index; --i)
    {
        A[i] = tmp[i];
    }
    return left + right + count;
}


int InversePairs(vector<int> A, int n)
{
    //处理无效输入
    if (A.size() == 0 || n < 0)
        return 0;

    //辅助数组
    vector<int> tmp(n);
    for (int i = 0; i < n; ++i)
        tmp[i] = A[i];

    int count = InversePairsCore(A, tmp, 0, n - 1);
    return count;
}


int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,0};
    vector<int> v(arr, arr + sizeof(arr) / sizeof(arr[0]));
    int count = InversePairs(v, sizeof(arr) / sizeof(arr[0]));
    cout << count << endl;
    return 0;
}