動機

sorted list的index，就是前面有幾個比自己小

index也可以這樣用!?

Problem

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.

Example 2:

Input: nums = [-1]Output: [0]

Example 3:

Input: nums = [-1,-1]Output: [0,0]

 

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Sol

這題最巧妙的是利用sorted list的index，就是前面有幾個比自己小的特性

這樣只要從右手邊一個一個去插入，再看各自的index

5212 ms，優化開始 (感覺這題有被多加測資，看sol分布圖中的92ms的code，拿來跑時間與這個差不多阿)

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        l = []
        ret = []
        for n in reversed(nums):
            i = bisect_left(l,n)
            ret.append(i)
            l.insert(i,n)
        ret.reverse()
        return ret

Sol2: SortedList

insert的代價很大，換用SortedList

460 ms

from sortedcontainers import SortedList
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        l = []
        ret = []
        for n in reversed(nums):
            ret.append(bisect_left(l,n))
            l.add(n)
        ret.reverse()
        return ret