|
|
题目描述 两个排序的数组A和B分别含有m和n个数，找到两个排序数组的中位数，要求时间复杂度应为O(log (m+n))。 说明 中位数的定义： - 这里的中位数等同于数学定义里的中位数。
- 中位数是排序后数组的中间值。
- 如果有数组中有n个数且n是奇数，则中位数为A[(n-1)/2]A[(n?1)/2]。
- 如果有数组中有n个数且n是偶数，则中位数为 (A[n / 2] + A[n / 2 + 1]) / 2(A[n/2]+A[n/2+1])/2.
- 比如：数组A=[1,2,3]的中位数是2，数组A=[1,19]的中位数是10。
样例1
- 输入:
- A = [1,2,3,4,5,6]
- B = [2,3,4,5]
- 输出: 3.5
|
样例2
- 输入:
- A = [1,2,3]
- B = [4,5]
- 输出: 3
|
题解 分治法。时间复杂度 log(n + m)log(n+m)
这题是 面试高频题，除了分治法外，还有二分法等其他方法来解， 算法面试高频题班免费试听，攻略还有更多大厂常考题型。
- public class Solution {
- public double findMedianSortedArrays ( int A[], int B[]) {
- int n = A.length + B.length;
- if (n % 2 == 0) {
- return (
- findKth(A, 0, B, 0, n / 2) +
- findKth(A, 0, B, 0, n / 2 + 1)
- ) / 2.0;
- }
- return findKth(A, 0, B, 0, n / 2 + 1);
- }
- // find kth number of two sorted array
- public static int findKth ( int[] A, int startOfA,
- int[] B, int startOfB,
- int k){
- if (startOfA >= A.length) {
- return B[startOfB + k - 1];
- }
- if (startOfB >= B.length) {
- return A[startOfA + k - 1];
- }
- if (k == 1) {
- return Math.min(A[startOfA], B[startOfB]);
- }
- int halfKthOfA = startOfA + k / 2 - 1 < A.length
- ? A[startOfA + k / 2 - 1]
- : Integer.MAX_VALUE;
- int halfKthOfB = startOfB + k / 2 - 1 < B.length
- ? B[startOfB + k / 2 - 1]
- : Integer.MAX_VALUE;
- if (halfKthOfA < halfKthOfB) {
- return findKth(A, startOfA + k / 2, B, startOfB, k - k / 2);
- } else {
- return findKth(A, startOfA, B, startOfB + k / 2, k - k / 2);
- }
- }
- }
|
----------------------------
原文链接:https://blog.csdn.net/JiuZhang_ninechapter/article/details/104679136
程序猿的技术大观园：www.javathinker.net
[这个贴子最后由 flybird 在 2020-03-08 22:48:28 重新编辑]
|
|
Java技术网站 → 『 Java开发技术 』 → 『 数据结构和算法专题 』 → 谷歌面试算法题：两个排序数组的中位数
消息
查看
搜索
好友
邮件
复制
引用
IP: 已设置保密
