problem:

There are two sorted arrays?nums1?and?nums2?of size m and n respectively.

有兩個排序好的數列num1和num大小為m和n

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

找到這兩個數列中的中位數,其時間復雜度為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

solution:

中位數:就是有序數列中的一個數可以將數列分為長度相同的兩個部分,且一個部分的所有值都大于這個數,另一部分的所有值都小于這個數,我們稱這個數為中位數

?

既然是要找到中位數,那么正常遇到這種題,歸并排序后再通過判斷偶數和奇數來輸出中位數就可以了,但是其時間復雜度并不符合要求

但是我們發現題目給出的兩個數列是有序的,那么我們可以根據這個來進行劃分,首先我們已知中位數可以將所有數列都分為長度相同的兩個部分,那么我們可以假設

m+n/2為其中一半的長度,假設在num1這個數列中選取第i個數,那么對應的num2數列選取j個

其i,j滿足i+j = m-i+n-j

那么j = (m+n)/2-i

當num1的第i+1個數小于num2的第j個數的時候說明i應該向右側移動

當num2的第j+1個數小于num1的第i個數的時候說明i應該向左側移動

于此同時所謂的移動其實是用的二分法,對num1進行二分,尋找i的最合適的位置

最合適也就是,只需要滿足num1的第i+1個數大于num2的第j個,和num2的第j+1個大于num1的第i個

?

如果n+m為奇數,說明中位數為max(num1的第i個,num2第j個)

如果n+m為偶數,說明中位數為(max(num1的第i個,num2第j個)+min(num1的第i+1個,num2第j+1個))/2

代碼如下:

1 class Solution(object): 2 def findMedianSortedArrays(self, nums1, nums2): 3 """ 4 :type nums1: List[int] 5 :type nums2: List[int] 6 :rtype: float 7 """ 8 9 m = len(nums1) 10 n = len(nums2) 11 if(m>n): 12 nums1,nums2,m,n = nums2,nums1,n,m 13 imin = 0 14 imax = m 15 halflen = (n+m+1)/2 16 while(imin <= imax): 17 i = (imin+imax)/2 18 j = halflen - i 19 if(i<imax and nums1[i]<nums2[j-1]): 20 imin = i+1 21 elif(i>imin and nums2[j]<nums1[i-1]): 22 imax = i-1 23 else: 24 maxleft = 0 25 if(i==0): 26 maxleft = nums2[j-1] 27 elif(j==0): 28 maxleft = nums1[i-1] 29 else: 30 maxleft = max(nums1[i-1],nums2[j-1]) 31 if((n+m)%2==1): 32 return maxleft 33 minright = 0 34 if(i == m): 35 minright = nums2[j] 36 elif(j == n): 37 minright = nums1[i] 38 else: 39 minright = min(nums1[i],nums2[j]) 40 41 return (minright+maxleft)/2.0

?

轉載于:https://www.cnblogs.com/fzy0331-leetcodestudy/p/8406562.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的Median of Two Sorted Arrays的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。