Python Easy MergeSort solution - Any chance a BST solution in Python?


  • 0
    A
    class Solution(object):
        def countRangeSum(self, nums, lower, upper):
            """
            :type nums: List[int]
            :type lower: int
            :type upper: int
            :rtype: int
            """
            if len(nums) == 0:
                return 0
            
            from bisect import bisect_left, bisect_right 
            for i in range(1, len(nums)):
                nums[i] += nums[i-1]
            n = len(nums)
            def mergeSort(nums, lo, hi):
                if lo == hi:
                    return int(nums[lo] >= lower and nums[lo] <= upper), [nums[lo]]
                mid = lo + (hi - lo) // 2
                leftNums, leftList = mergeSort(nums, lo, mid)
                rightNums, rightList = mergeSort(nums, mid+1, hi)
                crossNums = 0
                for x in leftList:
                    crossNums += bisect_right(rightList, x+upper) - bisect_left(rightList, x+lower)
                totalList = []
                i, j = 0, 0
                while i < len(leftList) and j < len(rightList):
                    if leftList[i] < rightList[j]:
                        totalList.append(leftList[i])
                        i += 1
                    else:
                        totalList.append(rightList[j])
                        j += 1
                totalList += rightList[j:] if i == len(leftList) else leftList[i:]
                return leftNums+rightNums+crossNums, totalList
            return mergeSort(nums, 0, n-1)[0]
    

Log in to reply
 

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