315.md

315 Count of Smaller Numbers After Self

Description

link

---

Solution

从数列最右边开始，每来一个数字插入到当前已经排序好的数组当中，然后通过bisect得出有多少比它更小的，即为答案，本质就是merge sort

值得一提的是，当排列为 n-1 + n-2 + n-3 + ... + 1 的时候将会达到最差时间复杂度

---

Code

O(nlogn)

class Solution:
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        r = []
        for i in range(len(nums) - 1, -1, -1):
            bisect.insort(r, nums[i])
            nums[i] = bisect.bisect_left(r, nums[i])
        return nums