Python O(min(m, n)) solution, provide random 1000 test cases to verify algorithm


  • -1
    H

    you can use 'python 004.py' to execute random 1000 test cases to verify algorithm.

    #!/usr/bin/python
    
    import random
    import time
    
    class Solution(object):
        def findMedianSortedArrays(self, nums1, nums2):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: float
            """
            length = len(nums1) + len(nums2)
            if length % 2 == 0:
                return (self.find_k(nums1, nums2, length / 2) +
                        self.find_k(nums1, nums2, length / 2 + 1)) / 2.0
            else:
                return self.find_k(nums1, nums2, length / 2 + 1) * 1.0
    
        def find_k(self, nums1, nums2, K):
            if len(nums1) == 0:  return nums2[K-1]
            if len(nums2) == 0:  return nums1[K-1]
    
            mid1, mid2 = len(nums1) / 2, len(nums2) / 2
            if nums1[mid1] >= nums2[mid2]:
                if K >= mid1 + mid2 + 2:
                    return self.find_k(nums1, nums2[mid2+1:], K - mid2 - 1)
                else:
                    return self.find_k(nums1[:mid1], nums2, K)
            else:
                if K >= mid1 + mid2 + 2:
                    return self.find_k(nums1[mid1+1:], nums2, K - mid1 - 1)
                else:
                    return self.find_k(nums1, nums2[:mid2], K)
    
    def verify(idx, nums1, nums2, K, result):
        merged_num = sorted(nums1 + nums2)
        right_answer = 0.0
        if (len(merged_num) % 2 == 0):
            right_answer = (merged_num[K] + merged_num[K-1]) / 2.0
        else:
            right_answer = merged_num[K] * 1.0
    
        passed = right_answer == result
        if passed:
            if idx % 38 == 0:
                print '.'
            else:
                print '.',
        else:
            print("{}>your answer {} is wrong, right answer={}".format(idx, result, right_answer))
        return passed
    
    def test2_random(array_max_len, testcases_count):
        passed = True
    
        def random_array(length, maxvalue=100):
            a = [0] * length
            for idx in range(length):
                a[idx] = random.randrange(1, maxvalue)
            return sorted(a)
    
        t1 = time.localtime()
        for idx in range(testcases_count):
            nums1_len = random.randrange(1, array_max_len) if array_max_len > 1 else 1
            nums1 = random_array(nums1_len, array_max_len)
            nums2_len = random.randrange(1, array_max_len) if array_max_len > 1 else 1
            nums2 = random_array(nums2_len, array_max_len)
            K = (len(nums1) + len(nums2)) / 2
    
            so = Solution()
            result = so.findMedianSortedArrays(nums1, nums2)
            passed = verify(idx + 1, nums1, nums2, K, result)
            if not passed:
                break
    
        if passed:
            t2 = time.localtime()
            consuming = (time.mktime(t2) - time.mktime(t1))
            print("\npassed {} test cases, consuming {} seconds".format(testcases_count, consuming))
    
        return passed
    
    def test1_fix(nums1, nums2):
        K = (len(nums1) + len(nums2)) / 2
        so = Solution()
        result = so.findMedianSortedArrays(nums1, nums2)
        return verify(1, nums1, nums2, K, result)
    
    passed = True
    # if passed:  passed = test1_fix([1, 5, 7, 10, 30, 60], [2, 6, 8, 10, 15, 20])
    # if passed:  passed = test1_fix([19, 22, 30, 32, 41, 49, 85, 91], [17, 18, 27, 38, 46, 60, 86, 87])
    # if passed:  passed = test1_fix([1, 3], [2])
    # if passed:  passed = test1_fix([12, 13, 15], [2, 6])
    if passed:  passed = test2_random(random.randrange(1, 10000), 1000)

Log in to reply
 

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