1. 代码段小站首页
  2. 算法

leetcode4-寻找两个有序数组的中位数

彭晨涛 • • 算法 • 阅读 59

这道题我没想出符合条件的思路

原题

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例1：

nums1 = [1, 3] nums2 = [2]

则中位数是 2.0

示例2：

nums1 = [1, 2] nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解法

思想

二分查找合并后的数组中第k/2个数，排除法,参考 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/

代码

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
        return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  
    }

    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode4-%e5%af%bb%e6%89%be%e4%b8%a4%e4%b8%aa%e6%9c%89%e5%ba%8f%e6%95%b0%e7%bb%84%e7%9a%84%e4%b8%ad%e4%bd%8d%e6%95%b0/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年1月8日 22:45
下一篇 2020年1月9日 21:58

相关推荐

  • leetcode297-二叉树的序列化与反序列化

    原题 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。...

    彭晨涛 彭晨涛
    算法 2020年1月15日
    080

  • leetcode45-跳跃游戏II

    原题 原题 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输...

    彭晨涛 彭晨涛
    算法 2020年2月15日
    0110

  • leetcode365-水壶问题

    原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？ 如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升...

    彭晨涛 彭晨涛
    算法 2020年3月21日
    0180

  • 海量数据算法-BitMap介绍和实现

    作为一个有素质的程序员，在面试中（不是） 难免会遇到海量数据相关的问题，之前有注意过java.util下面有一个BitSet数据结构，但不是很明白是做什么用的。今天就来研究一下它背...

    彭晨涛 彭晨涛
    算法 2020年2月27日
    03280

  • leetcode1014-最佳观光组合

    原题 给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。 一对景点（i < j）组成的观光组合的得分为（A[i]...

    彭晨涛 彭晨涛
    算法 2020年6月17日
    01470

  • leetcode191-位1的个数

    原题 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。 示例 1： 输入： 000000000000000000000000...

    彭晨涛 彭晨涛
    算法 2020年4月15日
    090

  • leetcode221-最大正方形

    原题 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 ...

    彭晨涛 彭晨涛
    算法 2020年5月8日
    0100

  • leetcode40-组合总和II

    原题 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字...

    彭晨涛 彭晨涛
    算法 2020年5月2日
    0710

  • 程序员面试金典17.16-按摩师

    原题（来源Leetcode） 一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，...

    彭晨涛 彭晨涛
    算法 2020年3月24日
    0450

  • leetcode394-字符串解码

    原题 给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意...

    彭晨涛 彭晨涛
    算法 2019年12月13日
    080

发表回复

登录后才能评论