文档章节

两个排序数组求中位数

Finley.Hamilton
 Finley.Hamilton
发布于 2014/11/11 16:37
字数 487
阅读 1179
收藏 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

粉丝 4
博文 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
面试题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
leetcode-java题解(每天更新)

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

韩来明
2015/03/09
0
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

文件的压缩与解压(linux)

Linux下*.tar.gz文件解压缩命令 1.压缩命令:   命令格式:tar -zcvf 压缩后文件名.tar.gz 被压缩文件名 可先切换到当前目录下。压缩文件名和被压缩文件名都可加入路径。 2.解压缩命令: ...

qimh
30分钟前
3
0
invalid character found in the request target 异常

这个异常时因为Tomcat 9不支持请求格式出现“{”等非法字符的问题 因为tomcat版本问题遇到的坑,记录一下。 问题 今天由于要测试一下订单详情页的异步查询,在本地起了一个服务,发送的请求是...

edwardGe
35分钟前
4
0
发现抓包软件fiddler的bug

1个请求他跳转之后,直接400,被拦在了Apache,使用fiddler 的,replay requests 是同样的结果,但是replay composer确是正常的。 也就是说这replay requests 是发原来的包,replay composer...

NLGBZJ
45分钟前
1
0
linux screen 命令详解

shell关闭后, 主机仍然运行 screen命令 启动jenkins以后, screen, 然后按ctrl+a 再按d 这样暂停了子界面, 这时候回到了父界面 用screen –ls查看目前子界面的状态 [root@free /]# screen -l...

SuShine
46分钟前
4
0
mac机器切换无线网络导致网页不能打开的问题

问题: 公司和家里使用不同的WI-FI,每次从家到公司时自动切换网络后,公司的许多地址不能访问, ping域名是可以ping同的,但是网页却打不开... 问题分析: 初步猜想是DNS缓存的问题? 对于MAC系统没...

Lennie002
48分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部