算法学习—逆序对数量

📝题目描述

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1 ≤ n ≤ 100000，数列中的元素的取值范围 [1,10^9]。

输入样例：

6
2 3 4 5 6 1

输出样例：

5

---

🤔理解何为逆序对

首先，我们来理解一下什么是逆序对。简单来说，逆序对就是在一个数列中，前面的数比后面的数大。比如在数列 [2, 3, 4, 5, 6, 1] 中，2 和 1 就是一个逆序对，因为 2 > 1 且 2 在 1 的前面。

解题策略 🛠️

1. 策略①：暴力解决 💪

算法思路

在理解了逆序对的概念之后，很自然能想到可以直接使用逐个比较的策略进行求解：

分别将每个元素和其后面的所有元素进行逐个比较

• if 后面有比其小的元素: 逆序对数量++
• 重复直至最后一个元素

核心代码

// 暴力解决策略的核心代码
int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (a[i] > a[j]) {
            count++;
        }
    }
}

复杂度分析

需要使用两个for循环——$O(n^2)$

复杂度较高，在一些要求较高的情况下会报超时错误

小挑战：你能尝试用暴力解法解决这个问题吗？试试看，感受一下它的时间复杂度吧！😉

---

2. 策略②：运用「归并排序」的算法思想 🧠

（1）回顾「归并排序」算法原理

归并排序是一种经典的分治算法，它的核心思想是将一个数组分成两个子数组，分别对子数组进行排序，然后将两个有序的子数组合并成一个有序的数组。归并排序的时间复杂度是 $O(n \log n)$，比暴力解法高效得多。

（2）改动以求逆序对数量

原理分析

在归并排序的过程中，当我们合并两个有序的子数组时，如果左边的某个元素 a[i] 大于右边的某个元素 a[j]，那么 a[i] 和 a[j] 就构成了一个逆序对。不仅如此，由于左边的子数组是有序的，a[i] 后面的所有元素也都大于 a[j]，因此我们可以一次性计算出多个逆序对。

代码实现

#include <iostream>

using namespace std;

typedef long long LL; // 结果较大

const int N = 100010;
int n;
int a[N], temp[N];

// 求逆序对数量
LL rev_pair(int a[], int l, int r)
{
  if (l >= r)
    return 0;

  int mid = l + r >> 1;
  LL res = rev_pair(a, l, mid) + rev_pair(a, mid + 1, r);

  int i = l, j = mid + 1;
  int k = 0;
  while (i <= mid && j <= r)
  {
    if (a[i] <= a[j])
      temp[k++] = a[i++];
    else
    {
      temp[k++] = a[j++];
      // 当a[i]>a[j]时，对于a[j]：与[i, mid]区间内的元素可组成逆序对
      res += mid - i + 1;
    }
  }

  while (i <= mid)
    temp[k++] = a[i++];
  while (j <= r)
    temp[k++] = a[j++];

  for (int i = l, j = 0; i <= r; ++i, ++j)
    a[i] = temp[j];

  return res;
}

int main()
{
  cin >> n;

  for (int i = 0; i < n; ++i)
    cin >> a[i];

  LL res = rev_pair(a, 0, n - 1);

  cout << res << endl;

  return 0;
}

复杂度分析

归并排序的时间复杂度是 $O(n \log n)$，因此这个解法的时间复杂度也是 $O(n \log n)$，比暴力解法高效得多。