V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hakunamatata11
V2EX  ›  推广

[LintCode 题解] 阿里巴巴面试算法题:两个排序数组的中位数

  •  
  •   hakunamatata11 · 2020-03-11 17:17:57 +08:00 · 1162 次点击
    这是一个创建于 1556 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目描述

    两个排序的数组 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
    
    

    image.gif

    样例 2

    输入:
    A = [1,2,3]
    B = [4,5]
    输出: 3
    

    image.gif

    题解

    分治法。时间复杂度 log(n + m)log(n+m)

    这题是面试高频题,除了分治法外,还有二分法等其他方法来解,点击链接立即免费试听:https://www.jiuzhang.com/course/9/?utm_source=sc-v2ex-fks免费试听,攻略还有更多大厂常考题型。

    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);
            }
        }
    }
    

    image.gif

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   913 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 21:44 · PVG 05:44 · LAX 14:44 · JFK 17:44
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.