文档章节

两个排序数组求中位数

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

没有更多内容

加载失败,请刷新页面

加载更多

关于php的xdebug配置(编辑器vscode)

虽然说echo和print_r是公认的最实用的调试工具,但是效率真的没有可视化的直接断点那么高。这里简单介绍如果安装及配置xdebug for vscode 一、PHP环境处的配置 1、编译安装 下载及编译php,因...

元谷
36分钟前
7
0
heartbeat

http://www.linux-ha.org/doc/users-guide/_building_and_installing_heartbeat_from_source.html kaer@linux-sqlf:~/Reusable-Cluster-Components-glue--0a7add1d9996> ./configure --enabl......

李有常
46分钟前
1
0
shell 脚本 title 免写入

1、有时候写脚本,需要写一些注释信息或者备注之类,当每次都手写比较麻烦,可以写一个脚本,每次运行则自动写入这些信息,不需要在手动输入; 通过 EOF 嵌入文档的方式; [root@localhost_002 sh...

芬野de博客
53分钟前
3
0
FragmentPagerAdapter+ViewPager 更新问题

场景 存在一种需求,当用户系统中,属于某一组织的用户登录之后(或者账户切换),要求主页面显示不同的ViewPager + Fragment组合,并且要求app无需退出就能刷新组合以及组合中的页面。 此外...

IamOkay
53分钟前
3
0
Python有哪些常用的标准库?Python基础教程,第十一讲,常用标准库(一)

上一节课我们学习了如何自定义模块,大家可以定义自己的模块,但是项目中通常不允许我们自己造轮子,所以本节课主要学习Python的标准库,学习使用别人的轮子,由于标准库内容较多,所以我们分...

程序员补给栈
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部