给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例:
输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.
时间超限！！！
class Solution(object):
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if not nums:
return []
_max = max(nums)
_min = min(nums)
_dict = {}
res = []
for i in nums[::-1]:
_sum = 0
for j in range(_min, i):
if j in _dict:
_sum += _dict[j]
if i not in _dict:
_dict[i] = 0
_dict[i] += 1
res.append(_sum)
return res[::-1]
Binary Indexed Tree
class BinaryIndexedTree(object):
def __init__(self, n):
self.sums = [0] * (n + 1)
def update(self, i, val):
while i < len(self.sums):
self.sums[i] += 1
i += i & -i
def sum(self, i):
r = 0
while i > 0:
r += self.sums[i]
i -= i & -i
return r
class Solution(object):
def countSmaller(self, nums):
hashTable = {v: i for i, v in enumerate(sorted(set(nums)))}
tree, r = BinaryIndexedTree(len(hashTable)), []
for i in xrange(len(nums) - 1, -1, -1):
r.append(tree.sum(hashTable[nums[i]]))
tree.update(hashTable[nums[i]] + 1, 1)
return r[::-1]
