题目描述:
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]
.
题目大意:
给定一个整数数组nums,返回一个新的数组counts。数组counts的第i个元素counts[i]表示位于nums[i]右侧且小于nums[i]的元素个数。
实际上就是求逆序对的个数。
测试用例如题目描述。
解题思路:
解法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)
ft.add(iNums[i], 1)
return ans
class FenwickTree(object):
def __init__(self, n):
self.n = n
self.sums = [0] * (n + 1)
def add(self, x, val):
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):
树节点TreeNode记录下列信息:
- 元素值:val
- 小于该节点的元素个数:leftCnt
- 节点自身的元素个数:cnt
- 左孩子:left
- 右孩子:right
从右向左遍历nums,在向BST插入节点时顺便做统计
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
解法III 归并排序求逆序数 (Merge Sort):
参考StefanPochmann的答案:https://leetcode.com/discuss/73256/mergesort-solution
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
本文链接:http://bookshadow.com/weblog/2015/12/06/leetcode-count-of-smaller-numbers-after-self/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。
大睿-SCTrojan 发布于 2016年3月11日 12:38 #
我有一个问题:BST的Worst Case的时间复杂度是O(N^2)吗?
在线疯狂 发布于 2016年3月11日 19:27 #
对于特定的输入有可能,比如输入一个已经排好序的数组
adiggo 发布于 2016年3月22日 00:17 #
是不是应该使用self balanced binary tree.