文档章节

两个排序数组求中位数

Finley.Hamilton
 Finley.Hamilton
发布于 2014/11/11 16:37
字数 487
阅读 1185
收藏 3

题目

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)).

思路

  1. 丢掉一个最小的,丢掉一个最大的
  2. 如果剩下小于等于两个数字,可以从中得到中位数
  3. 标准写法不是这样的,是通过寻找第K小的数来实现的

该方法的核心是将原问题转变成一个寻找第k小数的问题(假设两个原序列升序排列),这样中位数实际上是第(m+n)/2小的数。所以只要解决了第k小数的问题,原问题也得以解决。 首先假设数组A和B的元素个数都大于k/2,我们比较A[k/2-1]和B[k/2-1]两个元素,这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。这两个元素比较共有三种情况:>、<和=。如果A[k/2-1]<B[k/2-1],这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。

#代码

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int aMinIndex = 0;
        int aMaxIndex = A.length - 1;
        int bMinIndex = 0;
        int bMaxIndex = B.length - 1;

        while (aMaxIndex - aMinIndex + 1 + (bMaxIndex - bMinIndex + 1) > 2) {

            boolean minInA = true;
            boolean maxInA = true;

            // drop the minimum one
            if (aMaxIndex >= aMinIndex && bMaxIndex >= bMinIndex) {
                minInA = A[aMinIndex] < B[bMinIndex];
            } else if ( bMaxIndex >= bMinIndex ) {
                minInA = false;
            }

            int useless = minInA?aMinIndex++:bMinIndex++;

            // drop the maximum one
            if (aMaxIndex >= aMinIndex && bMaxIndex >= bMinIndex) {
                maxInA = A[aMaxIndex] > B[bMaxIndex];
            } else if ( bMaxIndex >= bMinIndex ) {
                maxInA = false;
            }

            useless = maxInA?aMaxIndex--:bMaxIndex--;
        }

        //System.out.println(A[aMinIndex] + " " + A[aMaxIndex]);
        //System.out.println(B[bMinIndex] + " " + A[bMaxIndex]);

        if (aMaxIndex == aMinIndex && bMaxIndex == bMinIndex) {
            return (A[aMaxIndex] + B[bMaxIndex]) * 1.0 / 2;
        } else if (aMaxIndex == aMinIndex){
            return A[aMaxIndex];
        } else if (bMaxIndex == bMinIndex) {
            return B[bMaxIndex];
        } else if (aMaxIndex - aMinIndex == 1) {
            return (A[aMinIndex] + A[aMaxIndex]) * 1.0 / 2;
        } else if (bMaxIndex - bMinIndex == 1) {
            return (B[bMinIndex] + B[bMaxIndex]) * 1.0 / 2;
        }
        return -1;
    }
}

© 著作权归作者所有

Finley.Hamilton

Finley.Hamilton

粉丝 5
博文 45
码字总数 15431
作品 0
广州
私信 提问
两个排序数组的中位数

原题   There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+......

一贱书生
2016/12/06
12
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
0
4
如何使用简单的 SQL 查询在 MySQL 中计算中位数

什么是中位数? 数值型数组的中位数是在数据排序后位于数组中间项的值。如果数组有偶数个元素,中位数就是最中间的两个数值的平均数。 中位数对于了解“我的值是否位于中间?”非常有用。比如...

oschina
2017/09/28
3.3K
3
面试题29:数组中出现次数超过一半的数字

题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。 分析...

嗯哼9925
2017/12/19
0
0
两个有序数组求中位数的O(logn)算法

好好地写写这个题目的解法吧。 由于复杂度是logn的,所以考虑要用到二分。 首先,假设两个数组的长度都是奇数,而且大于1。令mid 为 (1 + n) / 2,也就是中间的那个元素的下标。考虑一下X[m...

m2012
2012/05/19
0
1

没有更多内容

加载失败,请刷新页面

加载更多

Guava RateLimiter + AOP注解实现单机限流、统计QPS

1、基于springboot项目pom.xml添加如下依赖: <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-aop</artifactId></dependency><d......

铁骨铮铮
18分钟前
3
0
龙芯版办公软件下载

金山wps office   rpm包:http://ftp.loongnix.org/os/loongnix/1.0/os/Packages/w/wps-office-10.8.0.6472-1.a20p1.mips64el.rpm   deb包:http://packages.deepin.com/loongson/pool/......

gugudu
23分钟前
2
0
BI报表分析和数据可视化,推荐这三个开源工具!

开源篇 一、Superset 1、技术架构:Python + Flask + React + Redux + SQLAlchemy 2、使用人群: (1)开发/分析人员做好看板,业务人员浏览看板数据 (2)业务人员可自行编辑图表,查看满足...

飓风2000
30分钟前
1
0
CountDownLatch

CountDownLatch的概念 CountDownLatch是一个同步工具类,用来协调多个线程之间的同步,或者说起到线程之间的通信(而不是用作互斥的作用)。 CountDownLatch能够使一个线程在等待另外一些线程...

少年已不再年少
39分钟前
1
0
centos7 新手阿里云服务器安装mongodb

简介 MongoDB 是一个基于分布式 文件存储的NoSQL数据库 由C++语言编写,运行稳定,性能高 旨在为 WEB 应用提供可扩展的高性能数据存储解决方案 MongoDB特点 模式自由 :可以把不同结构的文档存...

醉雨
49分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部