Leetcode 315. Count of Smaller Numbers After Self

Tyan

发布于 2021-07-15 14:05:33

4630

发布于 2021-07-15 14:05:33

文章被收录于专栏：SnailTyanSnailTyan

1. Description

2. Solution

**解析：**Version 1，从右往左遍历数组，每次都将数据放到有序序列里，使用二分查找寻找数据所在的位置，索引位置即为右侧小于数据的个数。

Version 1

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        order = []
        for i in range(n-1, -1, -1):
            index = bisect.bisect_left(order, nums[i])
            ans[i] = index
            order.insert(index, nums[i])
        return ans