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

• 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)
if (len(merged_num) % 2 == 0):
right_answer = (merged_num[K] + merged_num[K-1]) / 2.0
else:

if passed:
if idx % 38 == 0:
print '.'
else:
print '.',
else:
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)``````

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