算法笔记--计算右侧小于当前元素的个数

2022-05-06 约 520 字预计阅读 2 分钟次阅读

这里写一下我的解题心路历程。（吐槽：c++的 multiset 红黑树比 vector 二分插入还慢，c++不等式 O(logN) > O(N), 麻了）

multiset 红黑树搜索 (58 / 65 个通过测试用例)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        multiset<int> ms;
        vector<int> ans(nums.size());
        for(int i=nums.size()-1; i>=0; i--) {
            ans[i] = distance(ms.begin(), ms.lower_bound(nums[i]));
            ms.insert(nums[i]);
        }
        return ans;
    }
};

vector 二分查找和插入 (62 / 65 个通过测试用例), 这里如果用 python 写就过了, 耗时 2916 ms

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findPos(vector<int>& data, int k) {
        int left = 0, right = data.size();
        while(right>left) {
            int mid = left+ (right-left)/2;
            if(k>data[mid]) left = mid+1;
            else right = mid;
        }
        return left;
    }

    vector<int> countSmaller(vector<int>& nums) {
        vector<int> ans(nums.size());
        vector<int> data;
        for(int i=nums.size()-1; i>=0; i--) {
            int pos = findPos(data, nums[i]);
            ans[i] = pos;
            data.insert(data.begin()+ pos, nums[i]);
        }
        return ans;
    }
};

桶排序加 vector 二分 (460 ms)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int findPos(vector<int>& data, int k) {
        int left = 0, right = data.size();
        while(right>left) {
            int mid = left+ (right-left)/2;
            if(k>data[mid]) left = mid+1;
            else right = mid;
        }
        return left;
    }

    vector<int> countSmaller(vector<int>& nums) {
        vector<int> ans(nums.size());
        int minData = nums[0], maxData = nums[0];
        for(auto e:nums) {
            minData = min(minData, e);
            maxData = max(maxData, e);
        }
        int bucketSize = sqrt(maxData - minData + 1);
        int bucketCnt = (maxData - minData + 1) / bucketSize + 1;
        vector<vector<int>> buckets(bucketCnt);
        for(int i=nums.size()-1; i>=0; i--) {
            int bucketId = (nums[i]-minData)/bucketSize;
            int pos = findPos(buckets[bucketId], nums[i]);
            buckets[bucketId].insert(buckets[bucketId].begin()+pos, nums[i]);
            for(int j=0;j<bucketId;j++) {
                ans[i] += buckets[j].size();
            }
            ans[i] += pos;
        }
        return ans;
    }
};

桶加 multiset 红黑树(1152 ms)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
  vector<int> countSmaller(vector<int>& nums) {
    vector<int> ans(nums.size());
    int minData = nums[0], maxData = nums[0];
    for (auto e : nums) {
      minData = min(minData, e);
      maxData = max(maxData, e);
    }
    int bucketSize = sqrt(maxData - minData + 1);
    int bucketCnt = (maxData - minData + 1) / bucketSize + 1;
    vector<multiset<int>> buckets(bucketCnt);

    for (int i = nums.size() - 1; i >= 0; i--) {
      int bucketId = (nums[i] - minData) / bucketSize;
      int pos =
          distance(buckets[bucketId].begin(), buckets[bucketId].lower_bound(nums[i]));
      buckets[bucketId].insert(buckets[bucketId].begin(), nums[i]);
      for (int j = 0; j < bucketId; j++) ans[i] += buckets[j].size();
      ans[i] += pos;
    }
    return ans;
  }
};

目录

算法笔记--计算右侧小于当前元素的个数