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
return ret[::-1]
def getindex(self,num):
start,end = 0,len(self.sorted)-1
while start <=end:
mid = (start+end)/2
if self.sorted[mid] < num:
start = mid+1
elif self.sorted[mid] > num:
end = mid-1
else:
return mid
return start

Accepted answer, the runtime is very long, the only difference is use a tree structure instead of an array, during the insertion if the value is greater than node value, then the value goes to the right of current node, during the insertion num means how many numbers is less than the node.val + 1, if it's less than it goes left, it's not easy to fully understand
Reference
https://leetcode.com/discuss/73280/my-simple-ac-java-binary-search-code

Runtime: 696 ms

import sys
class TreeNode:
def __init__(self,val):
self.val = val
self.num = 0
self.left = None
self.right = None
class Solution(object):
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
l = len(nums)
i = l-1
self.sorted = []
ret = []
root = TreeNode(sys.maxint)
while i>=0:
num = nums[i]
index = self.getindexbst(root,num,0)
ret.append(index)
i-=1
return ret[::-1]
def getindexbst(self,node,val,num):
if val <= node.val:
node.num +=1
if node.left:
return self.getindexbst(node.left,val,num)
else:
node.left = TreeNode(val)
node.left.num = 1
return num
else:
num += node.num
if node.right:
return self.getindexbst(node.right,val,num)
else:
node.right = TreeNode(val)
node.right.num = 1
return num