Count of Smaller Numbers After Self
Count of Smaller Numbers After Self First I thought start from the end, for each element look right and find the first number which is smaller than it, then c[current] = c[firstsmall]+1, it turns out to be wrong in case [2,0,1], the correct should be move from the end and keep the array on the right of current element to be sorted, My first solution is insertion sort, but it results in time limit exceeds error, the complexity is nlg(n), if we don't consider the time used in copy array, to find the index where current number will be inserted is easy, just use the binary search, since it's already an sorted array class Solution(object): def countSmaller(self, nums): """ :type nums: List[int] :rtype: List[int] """ l = len(nums) i = l-1 self.sorted = [] ret = [] while i>=0: num = nums[i] index = self.getindex(num) self.sorted = self.sorted[:index]+[num]+self.sorted[index:] ret.append(index) i-=1...