Clean and easy BIT python solution


  • 0
    H

    Inspired by others but rewrite in a cleaner way.

    class Solution(object):
        def countSmaller(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            if not nums:
                return []
            padding = min(nums)
            if padding <= 0:
                nums = [n + 1 -padding for n in nums]
            mx = max(nums)
            T = [0] * (mx + 1)
            res = []
            def getSum(i):
                ans = 0
                while i:
                    ans += T[i]
                    i -= i &(-i)
                return ans
            def update(i):
                while i < len(T):
                    T[i] += 1
                    i += i &(-i)
            for n in nums[::-1]:
                res.append(getSum(n-1))
                update(n)
            return res[::-1]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.