Count of Smaller Numbers After Self LeetCode solution in C++

1
class Solution {
2
 protected:
3
  void merge_countSmaller(vector<int> &indices, int first, int last, vector<int> &results,
4
                          vector<int> &nums) {
5
    int count = last - first;
6
    if (count > 1) {
7
      int step = count / 2;
8
      int mid = first + step;
9
      merge_countSmaller(indices, first, mid, results, nums);
10
      merge_countSmaller(indices, mid, last, results, nums);
11
      vector<int> tmp;
12
      tmp.reserve(count);
13
      int idx1 = first;
14
      int idx2 = mid;
15
      int semicount = 0;
16
      while ((idx1 < mid) || (idx2 < last)) {
17
        if ((idx2 == last) || ((idx1 < mid) && (nums[indices[idx1]] <= nums[indices[idx2]]))) {
18
          tmp.push_back(indices[idx1]);
19
          results[indices[idx1]] += semicount;
20
          ++idx1;
21
        } else {
22
          tmp.push_back(indices[idx2]);
23
          ++semicount;
24
          ++idx2;
25
        }
26
      }
27
      move(tmp.begin(), tmp.end(), indices.begin() + first);
28
    }
29
  }
30

31
 public:
32
  vector<int> countSmaller(vector<int> &nums) {
33
    int n = nums.size();
34
    vector<int> results(n, 0);
35
    vector<int> indices(n, 0);
36
    iota(indices.begin(), indices.end(), 0);
37
    merge_countSmaller(indices, 0, n, results, nums);
38
    return results;
39
  }
40
};