这里写一下我的解题心路历程。(吐槽: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;
}
};
|
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;
}
};
|
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;
}
};
|