LeetCode 315. 计算右侧小于当前元素的个数
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example 1:
Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Constraints:
- 0 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
解题思路
- 使用二分查找优化的插入排序
- 二叉搜索树
- 归并排序
- 树状数组
- 线段树
参考代码
/*
* @lc app=leetcode id=315 lang=cpp
*
* [315] Count of Smaller Numbers After Self
*/
// @lc code=start
class Solution {
public:
// Insertion Sort with binary search optimization
vector<int> countSmaller(vector<int>& nums) {
if (nums.empty()) return {};
size_t n = nums.size();
vector<int> res(n);
res[n-1] = 0;
for (int i=n-2; i>=0; i--) {
// find the 1st elements less than val
int val = nums[i];
int l = i+1, r = n;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] >= val) {
l = m + 1;
} else {
r = m;
}
} // upper_bound in descending array
// return l;
for (int j = i; j + 1 < l; j++) {
nums[j] = nums[j+1];
}
nums[l-1] = val;
res[i] = n-l;
}
return res;
} // AC, runtime beats 5.07 % of cpp submissions
};
// @lc code=end
注意：使用开区间，这样区间只有两个元素的时候选择的mid是第二个元素，避免了nums[m] < val时更新r = m的死循环。