逆序数算法

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

然后,我们更改传参,把整体计数变成分别计数即可。