Python divide & conquer and DP

  • 3

    Probably replace the binary search with liear search would be faster.
    The idea is quit simple,

    Here is an example
    Now consider we are trying to find all elements (<2*n - 1) for 5 at index 0.

    if we divide it into two parts [5,1,4], [2,5,2], then we sort the right part.
    it becomes [2,2,5], since we only need to consider the elements after index 0, also the right array has been sorted, if the found the last element that satisfies the condition, then all the elements before this element would be the result.

    And how do we handle the "1" on the left array? since it is also meet the condition. Well it has been handled by the recursive call.

    This code is also used DP, since the left hand side array was also sorted, we can save the result for the previous smaller integer, then we only need to consider the elements after the point where the previous iteration stops.

    class Solution(object):
        def reversePairs(self, nums):
            return self.helper(nums, 0, len(nums))
        def helper(self, nums, l, r):
            mid = l + r >> 1
            if mid == l: return 0
            total = self.helper(nums, l, mid) + self.helper(nums, mid, r)
            prev_total = 0
            for i in range(l, mid):
                target = nums[i] - 1 >> 1
                idx = bisect.bisect_right(nums, target, mid, r)
                prev_total += idx - mid
                mid = idx
                total += prev_total
            nums[l: r] = sorted(nums[l: r])
            return total

  • 0

    Your method is simply merge sort, not necessary DP

  • 0

    I am saving the previous computed result and reuse it to avoid recompute, this is DP
    prev_total += idx - mid

  • 0

    Not sure that qualifies as dp. Also the sorting is done using native sort instead of merge sort. Your runtime should scale > O(nlogn)

  • 0

    @devilhtc python native sorting algorithm is timsort, which runs in O(n) for each subset in our case.

  • 0
    target = nums[i]/2.0
    index = bisect_left(nums, target, mid, r)

    would be easier to understand!

Log in to reply

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