计算右侧小于当前元素的个数

Pluveto

Dec 03, 2021 发布

? 次浏览

逆序数算法

Naive solution:

class Solution {
public:
  vector<int> countSmaller(vector<int> &nums) {
    int n = nums.size();
    std::vector<int> ret(n);
    for (int i = 0; i < n; i++) {
      int cnt = 0;
      for (int j = i + 1; j < n; j++) {
        if (nums[j] < nums[i]) {
          cnt++;
        }
      }
      ret[i] = cnt;
    }
    return ret;
  }
};

超时。

我们先考虑一种简单的情况：求整体的逆序数。举个例子：

    7 4 1 2 6 5 8 9
// 分治
   7 4 1 2      6 5 8 9
 7 4   1 2      6 5   8 9
// 归并时统计逆序数
4 7    1 2      5 6    8 9
+1                     +1          <-- 逆序数

// 左侧：
1 2 4 7 // 1 插入到 4 前，逆序数 ++ ->2
        // 2 插入到 4 前，逆序数 ++ ->3
// 右侧：
5 6 8 9 // 逆序数不变 -> 1

// 目前逆序数和：4

// 最后一轮归并：
1 2 4 5 6 7 8 9

// 双指针过程：

1 2 4 7 // 逆序数 ++
    ^
5 6 8 9
^
1 2 4 5
    7 // 逆序数 ++
    ^
  6 8 9 // 逆序数 ++
  ^
1 2 4 5 6 7 8 9
// 目前逆序数和：7