Share my divide and conquer solution


  • 0
    Y
    class Solution(object):
        def countSmaller(self, nums):
            tmp = [0]*len(nums)
            counts = [0]*len(nums)
            pairs = [(nums[i], i) for i in range(len(nums))]
            def count(lo, hi):
                if hi <= lo: return
                mid = (lo + hi)/2
                count(lo, mid) 
                count(mid + 1, hi)
                i, j, k = lo, mid + 1, lo
                for i in range(lo, mid + 1):
                    while j <= hi and pairs[j][0] < pairs[i][0]:
                        tmp[k] = pairs[j]
                        k += 1
                        j += 1
                    counts[pairs[i][1]] += (j - 1 - mid)
                    tmp[k] = pairs[i]
                    k += 1
                pairs[lo:k] = tmp[lo:k]
            count(0, len(nums) - 1)
            return counts
    

Log in to reply
 

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