LeetCode 高级 - 计算右侧小于当前元素的个数_py3 计算右侧小于当前元素的个数

作者：盐析白兔 | 2024-02-15 21:29:34

踩

py3 计算右侧小于当前元素的个数

计算右侧小于当前元素的个数

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5的右侧有 2 个更小的元素 (2 和 1).
2的右侧仅有 1 个更小的元素 (1).
6的右侧有 1 个更小的元素 (1).
1的右侧有 0 个更小的元素.1
2
3
4
5
6
7

比较明显的一种思路是倒序遍历原数组，并将元素升序排列插到一个新数组，这样当元素第一次插入到新数组时的下标就是该元素右侧小于该元素的个数。（第一次是由于后续该位置可能被别的元素抢占）。

然而在这里暴力解决显然不合适，因此插入到新数组的过程我们采取二分搜索的方式。

参考
http://www.cnblogs.com/xidian2014/p/8831344.html

class Solution {
    1
2

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/87161