There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3] nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
解法:
我采用的解法是用2个变量分别指向两个数组,每次取较小的一个,然后将其指针后移动,直至找到中位数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
class : def findMedianSortedArrays (self, nums1, nums2) : """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ if (len(nums1) == 0 ): if (len(nums2)%2 != 0 ): return nums2[int(len(nums2)/2 )]; else : result1 = nums2[int(len(nums2)/2 -1 )]; result = nums2[int(len(nums2)/2 )]; result = (result+result1)/2 ; return result; if (len(nums2) == 0 ): if (len(nums1) % 2 != 0 ): return nums1[int(len(nums1) / 2 )]; else : result1 = nums1[int(len(nums1) / 2 - 1 )]; result = nums1[int(len(nums1) / 2 )]; result = (result + result1) / 2 ; return result; t = len(nums1) + len(nums2); if (t % 2 != 0 ): pos = t / 2 ; flag = 0 ; else : pos1 = t / 2 - 1 ; pos2 = t / 2 ; flag = 1 ; i = 0 ; j = 0 ; k = 0 ; result = -1 ; while (i < len(nums1) or j < len(nums2)): if (i == len(nums1)): result = nums2[j]; j+=1 ;k+=1 ; elif (j == len(nums2)): result = nums1[i]; i += 1 ; k += 1 ; elif (nums1[i] < nums2[j]): result = nums1[i]; i += 1 ; k += 1 ; elif (nums1[i] > nums2[j]): result = nums2[j]; j += 1 ; k += 1 ; else : result = nums1[i]; i += 1 ; k += 2 ; j += 1 ; if (flag == 0 and k > pos): return result; if (flag == 1 and k > pos1): if (i == len(nums1) and j == len(nums2)): return result; if (i == len(nums1)): result1 = nums2[j]; result = (result + result1) / 2.0 ; return result; if (j == len(nums2)): result1 = nums1[i]; result = (result + result1) / 2.0 ; return result; if (nums1[i] < nums2[j]): result1 = nums1[i]; else : result1 = nums2[j]; result = (result + result1) / 2.0 ; return result;
还可以采用分治法解决该问题 参考链接:http://blog.csdn.net/hk2291976/article/details/51107778
近期评论