文档章节

Median of Two Sorted Arrays

一个能打的都没有
 一个能打的都没有
发布于 2014/08/18 13:50
字数 712
阅读 3248
收藏 0

①原题

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

②乡村英语翻译一下

给你两个排序数组,容量为m的数组A,容量为n的数组B。求出两个数组的中位数(啥玩意?),硬性要求时间复杂度O(log (m+n)).

③读题

1:太汗颜了,median到底是个啥,查一下:

中位数是在一组数据中居于中间的数(特别注意的地方是:这组数据之前已经经过升序排列!!!),即在这组数据中,有一半的数据比它大,有一半的数据比它小。如果这组数据包含偶数个数字,中值是位于中间的两个数的平均值。

2:好吧,中位数是这么个玩意,那么理论上首先我们需要先将两个数组合为一,再求这个新合并的数组的中位数。

3:但是,已经限定死了时间复杂度为log(m+n),原来LeetCode的题目也思路不开放嘛。

4:问题可以转化成两个有序序列找第num大的数,由于时间复杂度已经限定死了,只能采用类似二分的思想,每个步骤去掉一半数据元素。

④解题

  public class MedianofTwoSortedArrays2 {
    //先来一个蠢的,实现功能。其实效率还是可以的嘛,只不过不符合算法要求,时间复杂度在于排序的 n*log(n)
    public static double findMedianLow(int A[], int B[]) {
        int[] sumArray = ArrayUtils.addAll(A, B);
        Arrays.sort(sumArray);
        int length = sumArray.length;
        if (length % 2 == 0) {
            double num1 = sumArray[length / 2];
            double num2 = sumArray[length / 2 - 1];
            return (num1 + num2) / 2;
        } else {
            return sumArray[length / 2];
        }
    }

    public static double findMedianSortedArrays(int A[], int B[]) {
        int m = A.length;
        int n = B.length;
        int total = m + n;
        //长度为积数取中间,为偶数去中间两个的平均值
        if ((total & 0x01) != 0) {
            return findMedian(A, m, B, n, total / 2 + 1);
        } else {
            return (findMedian(A, m, B, n, total / 2) + findMedian(A, m, B, n,
                    total / 2 + 1)) / 2.0;
        }
    }

    //二分法,每次都能去除掉一部分范围外数据。需要注意每次去除数据都会改变数组的结构,所以需要特殊处理临界值
    private static double findMedian(int A[], int m, int B[], int n, int target) {
        if (m == 0) {
            return B[target - 1];
        } else if (n == 0) {
            return A[target - 1];
        } else if (target == 1) {
            return A[0] < B[0] ? A[0] : B[0];
        }
        int temp = target / 2;
        if (Math.min(m, n) < temp) {
            temp = Math.min(m, n);
        }
        if (A[temp - 1] > B[temp - 1]) {
            return findMedian(A, m, Arrays.copyOfRange(B, temp, n), n - temp, target - temp);
        } else if (A[temp - 1] < B[temp - 1]) {
            return findMedian(Arrays.copyOfRange(A, temp, m), m - temp, B, n, target - temp);
        } else {
            return A[temp - 1];
        }
    }

    public static void main(String[] args) {
        int[] a = new int[10000];
        int[] b = new int[20000];
        for (int i = 0; i < 10000; i++) {
            a[i] = i + 1;
        }
        for (int i = 10000; i < 30000; i++) {
            b[(i - 10000)] = i + 1;
        }
        long nowTime = System.currentTimeMillis();
        System.out.println(MedianofTwoSortedArrays2.findMedianLow(a, b));
        System.out.println(System.currentTimeMillis() - nowTime);
        long nowTime1 = System.currentTimeMillis();
        System.out.println(MedianofTwoSortedArrays2.findMedianSortedArrays(a, b));
        System.out.println(System.currentTimeMillis() - nowTime1);
    }
}


© 著作权归作者所有

上一篇: Linux 命令之 chmod
下一篇: Two Sum
一个能打的都没有
粉丝 5
博文 14
码字总数 5548
作品 0
朝阳
高级程序员
私信 提问
加载中

评论(4)

gywgg
gywgg
findMedian函数里面,最后那个else return A[temp - 1];
考虑到之前有可能因为 target 比 m 或者 n 要大,然后给target赋了新值。
这一步可能导致找到的东西不是我们想要的那个值。
比如说这两个数列
[ 1 ] , [1,2,3,4,5,6,7,8,9, 10]
m = 1; n = 10;
target 被强行赋值为 1,接下来发现A[ 0 ] == B[ 0 ] == 1; 这里就直接return了。实际上中位数可不是在这里
gywgg
gywgg
findMedian函数里面,最后那个else return A[temp - 1];
考虑到之前有可能因为 target 比 m 或者 n 要大,然后给target赋了新值。
这一步可能导致找到的东西不是我们想要的那个值。
比如说这两个数列
1, [1,2,3,4,5,6,7,8,9, 10]
m = 1; n = 10;
target 被强行赋值为 1,接下来发现A0 == B0 == 1; 这里就直接return了。实际上中位数可不是在这里
一个能打的都没有
一个能打的都没有 博主

引用来自“dan定”的评论

A[] = {1,2};
B[] = {1,2};
?
d
dan定
A[] = {1,2};
B[] = {1,2};
LeetCode 004 Median of Two Sorted Arrays 详细分析

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

被称为L的男人
2018/11/24
0
0
【Leetcode】4. Median of Two Sorted Arrays

1.英文题目 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......

啊哈关关
2018/11/06
18
0
[leetcode] Median of Two Sorted Arrays

https://oj.leetcode.com/problems/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 ove......

jdflyfly
2014/06/24
1K
0
Leetcode_Problem4_Median of Two Sorted Arrays(两种解法)

题目 问题网址: https://leetcode.com/problems/median-of-two-sorted-arrays/description/ 问题描述: There are two sorted arrays nums1 and nums2 of size m and n respectively. Find......

quiet_girl
2018/01/31
0
0
LeetCode 4.Median of Two Sorted Arrays

Median of Two Sorted Arrays 写晕了,但是 AC 了。 因为题目要求的时间复杂度,O(log (m+n)). 主要思想就是二分法,先二分数组1,放入数组2判断是否符合中位数条件,如果不符合就依据条件继...

费城的二鹏
2018/11/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

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

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部