问题描述
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].
问题分析
是一道hard题，还是有点难度。
问题求某数字右边比其小的数，可以看做求逆序数，用归并排序的思路来做。参考了LeetCode Discuss。
归并left和right数组时，当选择left中的元素进行归并时，right中已经选择的元素个数即为比该元素小的，因此其逆序数应加相应个数。
网上还有做法提到Fenwick Tree的，但是我还没看懂...弱哭...
AC代码
class Solution(object):
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
smaller = [0 for i in range(len(nums))]
self.sort(list(enumerate(nums)), smaller)
return smaller
def sort(self, enum, smaller):
mid = len(enum)/2
if not mid:
return enum
left, right = self.sort(enum[:mid], smaller), self.sort(enum[mid:], smaller)
p = q = 0
m, n = len(left), len(right)
while p < m or q < n:
if q == n or p < m and left[p][1] <= right[q][1]:
enum[p+q] = left[p]
smaller[left[p][0]] += q
p += 1
else:
enum[p+q] = right[q]
q += 1
return enum
