文档章节

两个排序数组求中位数

Finley.Hamilton
 Finley.Hamilton
发布于 2014/11/11 16:37
字数 487
阅读 1180
收藏 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
面试题29:数组中出现次数超过一半的数字

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

嗯哼9925
2017/12/19
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
0
4
两个有序数组求中位数的O(logn)算法

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

m2012
2012/05/19
0
1
leetcode-java题解(每天更新)

说明:选用java,重在体会,性能不是最优。欢迎转载:http://www.ming-yue.cn/leetcode-java-solutions/。 先给出一个leetcode的已有答案,为什么上来直接给出答案,因为这个好多答案写的都非...

韩来明
2015/03/09
0
1

没有更多内容

加载失败,请刷新页面

加载更多

SharedPreferences 的使用,commit和apply两个方法的区别

SharedPreferences sp = getSharedPreferences("config",MODE_PRIVATE); //第一个参数:存储文件的名称,第二个参数文件的访问权限,通常MODE_PRIVATE是私有存储 sp.edit().putString("USERNAM...

lanyu96
12分钟前
1
0
02-《Apache Tomcat 9 User Guide》之简介

1.Introduction - 介绍 For administrators and web developers alike, there are some important bits of information you should familiarize yourself with before starting out. This d......

飞鱼说编程
17分钟前
1
0
关于maven的使用,这一篇基本就够了

2.1 关于maven 每一个工具的出现都有其历史意义,而Maven的出现则是开发者对于不同的项目都要有自己的Ant构建文件,而这些文件都各不相同,而且JAR被检入CVS(Concurrent Version System),...

小小明童鞋
19分钟前
13
0
从xtrabackup完整备份恢复单个innodb表

现在大多数同学在线上采取的备份策略都是xtrabackup全备+binlog备份,那么当某天某张表意外的删除那么如何从xtrabackup全备中恢复呢?从mysql 5.6版本开始,支持可移动表空间(Transportable...

IT--小哥
23分钟前
1
0
百度AI攻城狮,用TensorFlow API训练目标检测模型(浣熊超可爱)

今天,人工智能正影响我们生产、生活的方方面面。10月10日,为期三天的2018华为全联接大会在上海拉开帷幕,此次大会以“+智能,见未来”为主题,发布了AI战略及全球领先的全栈全场景AI解决方...

Python唱情歌
24分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部