文档章节

LeetCode题解-4-Median of Two Sorted Arrays

蔡晓建
 蔡晓建
发布于 2017/02/22 09:52
字数 373
阅读 4
收藏 0

解题思路

这个题目是说在两个已排序的数组中找到中间的数,并且要求复杂度是O(ln(m+n))。看到这个复杂度要求,就不能使用简单的数组合并后取中间位置,而是要考虑类似二分法之类的算法。

算法的要点就是把题目转换成寻找第k个位置的数字,对于数组A和B,假设都长度都大于k/2,那么都取k/2的位置进行比较,假设A[k/2]小于B[k/2],那么A中k/2之前的位置都不可能是第k个位置,那么可以直接排除,问题转换成在A的k/2位置之后组成的数组和B数组中,寻找第k-k/2位置的数字。以此类推,就是一个递归实现了。

参考源码

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        if (total % 2 == 0) {
            return (findKth(total / 2, nums1, 0, nums2, 0) + findKth(total / 2 + 1, nums1, 0, nums2, 0)) / 2.0;
        } else {
            return findKth(total / 2 + 1, nums1, 0, nums2, 0);
        }
    }

    private int findKth(int k, int[] nums1, int s1, int[] nums2, int s2) {
        if (s1 >= nums1.length) {
            return nums2[s2 + k - 1];
        }
        if (s2 >= nums2.length) {
            return nums1[s1 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[s1], nums2[s2]);
        }
        int k1 = s1 + k / 2 - 1 < nums1.length ? nums1[s1 + k / 2 - 1] : Integer.MAX_VALUE;
        int k2 = s2 + k / 2 - 1 < nums2.length ? nums2[s2 + k / 2 - 1] : Integer.MAX_VALUE;
        if (k1 < k2) {
            return findKth(k - k / 2, nums1, s1 + k / 2, nums2, s2);
        } else {
            return findKth(k - k / 2, nums1, s1, nums2, s2 + k / 2);
        }
    }
}

© 著作权归作者所有

蔡晓建
粉丝 10
博文 25
码字总数 9436
作品 0
广州
高级程序员
私信 提问
求两递增数组的中位数(O(log(m + n)))你会吗?

原题可以在 LeetCode 上找到,地址:Median of Two Sorted Arrays,难度级别为困难。 不要被困难级别唬到,看完这篇文章,相信你也可以做出来。 乍一看求两递增数组的中位数并不是很难,因为...

Blankj
2017/12/11
0
0
LeetCode 004 Median of Two Sorted Arrays 详细分析

题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/ 我一直会卡在这道题上,在网上看了半个小时的博客,愣是没看懂。后来看到 YouTube 上有一个印度大哥的讲解,豁然开朗...

被称为L的男人
2018/11/24
0
0
[leetcode题解]Median of Two Sorted Arrays

4. Median of Two Sorted Arrays 题目 https://leetcode.com/problems/median-of-two-sorted-arrays/description/ 题意是给出两个有序的列表,找出它们合并之后的中位数(如果个数为偶数,则...

her0kings1ey
2017/12/17
0
0
算法题--寻找两个有序数组的中位数

题目描述 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示...

独孤求媛
10/11
0
0
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)). ②乡村......

一个能打的都没有
2014/08/18
3.2K
4

没有更多内容

加载失败,请刷新页面

加载更多

centos7 安装 mysql5.7 版本(全)

centos 安装 版本说明 :centos7,mysql5.7 ,不是 centos7 可能有些命令不兼容 安装 mysql-server # 下载并安装 mysql yum wget -i -c http://dev.mysql.com/get/mysql57-community-relea......

sanri1993
35分钟前
4
0
Spring3.x升级到Spring4.x-5.x时关于MappingJacksonHttpMessageConverter的报错问题

在Spring4.x或者以上的版本强使用(不然会报错): org.springframework.http.converter.json.MappingJackson2HttpMessageConverter 如果是Spring4.0获者以下的版本可以使用MappingJacksonH...

code-ortaerc
38分钟前
3
0
OSG 渲染状态污染到其它节点怎么解决?

在根节点补上初始状态

洛克人杰洛
40分钟前
4
0
grid 布局 设置行列间距

本文转载于:专业的前端网站➪grid 布局 设置行列间距 <!DOCTYPE html><html lang="zh"> <head> <meta charset="UTF-8" /> <meta name="viewport" content="widt......

前端老手
52分钟前
4
0
spring-data-elasticsearch 和 Jackson 配合使用的bug

下面先简单描述项目。 项目依赖: dependencies { implementation group: 'org.springframework.boot', name: 'spring-boot-starter-data-elasticsearch', version: '2.1.0.RELEASE'......

Landas
53分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部