Count of Smaller Numbers After Self

Question

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

Thoughts

一个概念inversion.

brute force O(n^2)

经典的merge sort

binary indexed tree

求右边小于当前值nums[i]的数，intuitve的想法就是把小于nums[i]的值的出现频率的sum 算出来。这个cumulative sum的概念就有点像binary indexed tree了。 而算这个值不能是每次都重新算，而应该用一个数据结构保存下来，在从右往走遍历的过程 中不断更新和query。

而如果我们是根据value来查找sum的话，必然不是很efficient, 因为需要查找很多不存在的value, 而查找小于nums[i]的数，除了用value来算，还可以用nums[i]在原数组中的排序顺序来算。

所以我们有了基本的想法,先找出对于每个i, nums[i]在原数组中的大小排序顺序，并且 需要先去重. 所以我们采取list->set->sort的方法.将每个value的排序后顺序存到一个 hashtable里。

然后对原数组从右往左遍历，过程中query和update.

segment tree

Solution

BIT

class BinaryIndexedTree(object):
    def __init__(self, maxVal):
        self.maxVal = maxVal
        self.tree = [0 for i in range(maxVal+1)]        

    def lowBit(self, x):
        return x & ~(x-1)

    def add(self, idx, val):
        while idx <= self.maxVal:
            self.tree[idx] += val
            idx += self.lowBit(idx)

    def read(self, idx):
        sum = 0
        while idx > 0:
            sum += self.tree[idx]
            idx -= self.lowBit(idx)
        return sum

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        length = len(nums)
        if length < 1:
            return []

        idx_map = {}
        for order, value in enumerate(sorted(set(nums))):
            idx_map[value] = order + 1 # order start from 1, cause bit start from 0 not -1

        bit = BinaryIndexedTree(length)
        result = [0 for i in range(length)]

        for i in range(length - 1, -1, -1):
            result[i] = bit.read(idx_map[nums[i]] - 1)
            bit.add(idx_map[nums[i]], 1)

        return result

References

• find inversion geeks