首页 > 代码库 > LeetCode——Median of Two Sorted Arrays
LeetCode——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)).
有两个已排序的数组A和B,大小为m 和 n。
找出两数组的中位数
时间复杂度应该为 O(log (m+n))。
简单粗暴的方法就是把两个数组合并成一个数组,排序,取中位数。但是用不到所给的已排序,也体现不了任何算法的意义。时间复杂度:O((m+n)log(m+n))。(不过此方法可以通过。)
public static double findMedianSortedArrays(int A[], int B[]) { int AB[] = new int[A.length + B.length]; for (int i = 0; i < A.length; i++) { AB[i] = A[i]; } for (int i = 0; i < B.length; i++) { AB[A.length + i] = B[i]; } Arrays.sort(AB); double median = AB.length % 2 == 1 ? AB[AB.length >> 1] : (AB[(AB.length - 1) >> 1] + AB[AB.length >> 1]) / 2.0; return median; }另一种思路:将此问题转换为在有序数组中寻找第K小的数的问题。直接抄了这里的实现。
public static double findMedianSortedArrays(int[] a, int[] b) { int m = a.length, n = b.length; int median = (m + n) / 2; if ((m + n) % 2 == 1) // Single median return findKthElement(a, b, median); else // Average of two medians return (findKthElement(a, b, median) + findKthElement(a, b, median - 1)) / 2.0; } private static double findKthElement(int[] a, int[] b, int k) { int m = a.length, n = b.length; int aStart = 0, bStart = 0; // Keep track of the starting index of both // arrays under consideration int ka, kb; while (true) { if (aStart == m) // a is empty; find the k-th element in b return b[bStart + k]; if (bStart == n) // b is empty; find the k-th element in a return a[aStart + k]; if (k == 0) // Find the smallest element return Math.min(a[aStart], b[bStart]); // Set the indices of the elements under consideration if (k == 1) { // A special case when k/2-1 < 0 ka = aStart; kb = bStart; } else { // Make sure the indices are within the boundaries ka = Math.min(m - 1, aStart + k / 2 - 1); kb = Math.min(n - 1, bStart + k / 2 - 1); } // Adjust k and the start index according to the relationship // between a[ka] and b[kb] if (a[ka] <= b[kb]) { // Any Element in a[aStart...ka] cannot be the one k -= ka - aStart + 1; aStart = ka + 1; } else { // Any Element in b[bStart...kb] cannot be the one k -= kb - bStart + 1; bStart = kb + 1; } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。