1365. 有多少小于当前数字的数字

class Solution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums) { vector<int> ans; int count = 0; for(int i=0; i<nums.size(); ++i) { for(int j=0; j<nums.size(); ++j) { if(nums[i] > nums[j]) { count++; } } ans.push_back(count); count = 0; } return ans; } };

可以看出暴力法的执行确实慢

class Solution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums) { int n = nums.size(); vector<pair<int,int> > tmp; tmp.clear(); vector<int> vec(n, 0); for (int i = 0;i < n; ++i) { tmp.push_back(make_pair(nums[i], i)); } sort(tmp.begin(), tmp.end()); int pre = -1; for (int i = 0;i < n; ++i) { if (i == 0) { vec[tmp[i].second] = pre + 1; } else if (tmp[i].first == tmp[i-1].first) { vec[tmp[i].second] = pre + 1; } else { pre = i - 1; vec[tmp[i].second] = pre + 1; } } return vec; } };