首页 > 代码库 > LeetCode里有特色的问题存档
LeetCode里有特色的问题存档
002* Median of Two Sorted Arrays
There are two sorted arrays A and B 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)).
1 class Solution: 2 def findKth(self, A, A_start, B, B_start, k): 3 if A_start >= len(A): 4 return B[B_start + k - 1] 5 if B_start >= len(B): 6 return A[A_start + k - 1] 7 if k == 1: 8 return min(A[A_start], B[B_start]) 9 A_key = 0x3f3f3f3f10 if A_start + k / 2 - 1 < len(A):11 A_key = A[A_start + k / 2 - 1]12 B_key = 0x3f3f3f3f13 if B_start + k / 2 - 1 < len(B):14 B_key = B[B_start + k / 2 - 1]15 if A_key < B_key:16 return self.findKth(A, A_start + k / 2, B, B_start, k - k / 2)17 else:18 return self.findKth(A, A_start, B, B_start + k / 2, k - k / 2)19 # @return a float20 def findMedianSortedArrays(self, A, B):21 n = len(A) + len(B)22 if n % 2 == 0:23 return (self.findKth(A, 0, B, 0, n / 2) + self.findKth(A, 0, B, 0, n / 2 + 1)) / 2.024 else:25 return self.findKth(A, 0, B, 0, n / 2 + 1)
出自算法导论9.3-8，设X[1..n]和Y[1..n]为两个数组，每个都包含n个已排好序的数。给出一个求数组X和Y中所有2n个元素的中位数的、O(lgn)时间算法。
1 int findMedian(int A[],int B[],int n,int low,int high) { 2 if (low > high) return NOT_FOUND; 3 else { 4 int k = (low+high)/2; 5 if (k==n && A[n]<=B[1]) return A[n]; 6 else if (k<n && B[n-k]<=A[k] && A[k]<=B[n-k+1]) return A[k]; 7 else if (A[k] > B[n-k+1]) return findMedian(A,B,n,low,k-1); 8 else return findMedian(A,B,n,k+1,high); 9 } 10 } 11 int twoArrayMedian(int X[],int Y[],int n) { 12 int median = findMedian(X,Y,n,1,n); 13 if (median==NOT_FOUND) median = findMedian(Y,X,n,1,n); 14 return median; 15 }
我们要取下中位数，注意到一个数x是中位数，当且仅当有n-1个数比x小，有n个数比x大，我们首先假设中位数在数组A中，二分中位数可能在的位置。
假设中位数所在区间为[L,R]，k为(L+R)/2。若A[k]是中位数，数组A中有k-1个数比A[k]小，n-k个数比A[k]大。若B中有n-k个数比A[k]小，有k个数比A[k]大，则A[k]是中位数。
由于B是已排序的，因此B[n-k]<=A[k]<=B[n-k+1]。
若A[k]>B[n-k+1]，则比A[k]小的数至少有n个，所以中位数小于A[k]，因此在区间[L,k-1]中。
反之则在区间[k+1,R]中。
若L>R，则中位数不在A中，对B数组进行同样的二分操作即可。
LeetCode里有特色的问题存档
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。