## 题目描述：

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:

Given nums = [5, 2, 6, 1]

```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.```

​Return the array `[2, 1, 1, 0]`.

## 解题思路：

### 解法I 树状数组 （Binary Indexed Tree / Fenwick Tree）：

1. 对原数组nums进行离散化处理（排序+去重），将nums从实数范围映射到 [1, len(set(nums))]，记得到的新数组为iNums

2. 从右向左遍历iNums，对树状数组的iNums[i]位置执行+1操作，然后统计(0, iNums[i])的区间和

## Python代码：

``````class Solution(object):
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
idxes = {}
for k, v in enumerate(sorted(set(nums))):
idxes[v] = k + 1
iNums = [idxes[x] for x in nums]
ft = FenwickTree(len(iNums))
ans = [0] * len(nums)
for i in range(len(iNums) - 1, -1, -1):
ans[i] = ft.sum(iNums[i] - 1)
return ans

class FenwickTree(object):
def __init__(self, n):
self.n = n
self.sums = [0] * (n + 1)

while x <= self.n:
self.sums[x] += val
x += self.lowbit(x)

def lowbit(self, x):
return x & -x

def sum(self, x):
res = 0
while x > 0:
res += self.sums[x]
x -= self.lowbit(x)
return res
``````

### 解法II 二叉搜索树 （Binary Search Tree）：

• 元素值：val
• 小于该节点的元素个数：leftCnt
• 节点自身的元素个数：cnt
• 左孩子：left
• 右孩子：right

## Python代码：

``````class Solution(object):
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
ans = [0] * len(nums)
bst = BinarySearchTree()
for i in range(len(nums) - 1, -1, -1):
ans[i] = bst.insert(nums[i])
return ans

class TreeNode(object):
def __init__(self, val):
self.leftCnt = 0
self.val = val
self.cnt = 1
self.left = None
self.right = None

class BinarySearchTree(object):
def __init__(self):
self.root = None

def insert(self, val):
if self.root is None:
self.root = TreeNode(val)
return 0
root = self.root
cnt = 0
while root:
if val < root.val:
root.leftCnt += 1
if root.left is None:
root.left = TreeNode(val)
break
root = root.left
elif val > root.val:
cnt += root.leftCnt + root.cnt
if root.right is None:
root.right = TreeNode(val)
break
root = root.right
else:
cnt += root.leftCnt
root.cnt += 1
break
return cnt
``````

## Python代码：

``````class Solution(object):
def countSmaller(self, nums):
def sort(enum):
half = len(enum) / 2
if half:
left, right = sort(enum[:half]), sort(enum[half:])
m, n = len(left), len(right)
i = j = 0
while i < m or j < n:
if j == n or i < m and left[i][1] <= right[j][1]:
enum[i+j] = left[i]
smaller[left[i][0]] += j
i += 1
else:
enum[i+j] = right[j]
j += 1
return enum
smaller = [0] * len(nums)
sort(list(enumerate(nums)))
return smaller
``````

Pingbacks已关闭。

1. 大睿-SCTrojan 发布于 2016年3月11日 12:38 #

我有一个问题：BST的Worst Case的时间复杂度是O(N^2)吗？

2. 在线疯狂 发布于 2016年3月11日 19:27 #

对于特定的输入有可能，比如输入一个已经排好序的数组

3. adiggo 发布于 2016年3月22日 00:17 #

是不是应该使用self balanced binary tree.