首页 > 代码库 > leetcode 4 Median of Two Sorted Arrays
leetcode 4 Median of Two Sorted Arrays
对于两个数组的折半查找
public class Solution { public double findMedianSortedArrays(int A[], int B[]) { int m = A.length, n = B.length; if (n == 0) { int mid = (m + 1) / 2; if (m % 2 == 0) { return (A[mid - 1] + A[mid]) / 2.0; } else { return A[mid - 1]; } } if (m == 0) { return findMedianSortedArrays(B, A); } if (m > 1) { if (A[1] < A[0]) { int temp = 0; for (int i = 0; i < m / 2; i++) { temp = A[i]; A[i] = A[m - 1 - i]; A[m - 1 - i] = temp; } } } if (n > 1) { if (B[1] < B[0]) { int temp = 0; for (int i = 0; i < n / 2; i++) { temp = B[i]; B[i] = B[n - 1 - i]; B[n - 1 - i] = temp; } } } if (A[m - 1] <= B[0]) { int mid = (m + n + 1) / 2; if ((m + n) % 2 == 0) { if (mid > m) { return (B[mid - m - 1] + B[mid - m]) / 2.0; } else if (mid == m) { return (A[m - 1] + B[0]) / 2.0; } else if (mid < m) { return (A[mid - 1] + A[mid]) / 2.0; } } else { if (mid <= m) { return A[mid - 1]; } else { return B[mid - m - 1]; } } } if (B[n - 1] <= A[0]) { return findMedianSortedArrays(B, A); } if (m > n) { return findMedianSortedArrays(B, A); } int length = (m + n) / 2 + 1; int la = 0, ra = m - 1; int ma = (la + ra) / 2, mb = length - (ma + 1) - 1; int pma = -1, pmb = -1; double med = 0; while (true) { if (A[ma] <= B[mb]) { if (ma < ra) { la = ma + 1; } else { break; } pma = ma; pmb = mb; ma = (la + ra) / 2; mb = length - (ma + 1) - 1; } else { if (ma > la) { ra = ma - 1; } else { break; } pma = ma; pmb = mb; ma = (ma + ra) / 2; mb = length - (ma + 1) - 1; } } if (pma > -1 && pmb > -1) { int[] rlts = { A[ma], B[mb], A[pma], B[pmb] }; Arrays.sort(rlts); if ((m + n) % 2 == 0) { med = (rlts[1] + rlts[2]) / 2.0; } else { med = rlts[2]; } } else { int[] rlts = { A[ma], B[mb]}; Arrays.sort(rlts); if ((m + n) % 2 == 0) { med = (rlts[1] + rlts[0]) / 2.0; } else { med = rlts[1]; } } return med; }}
leetcode 4 Median of Two Sorted Arrays
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。