No.004 Median of Two Sorted Arrays

4. Median of Two Sorted Arrays

  • Total Accepted: 104147
  • Total Submissions: 539044
  • Difficulty: Hard

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

Example 1:

nums1 = [1, 3]
nums2 = [2] 
The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

  其实整个思路应该就是将两个有序数组进行排序的过程,然后根据总个数的奇偶决定中位数是一个还是两个的平均值。
 1 public class No_4 {
 2     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 3         int total = nums1.length + nums2.length ;
 4         int [] res ;
 5         //判断最后的结果是单独一个数还是两个数的平均值
 6         if(total%2 == 1){
 7             res = new int [1] ;
 8         }else{
 9             res = new int [2] ;
10         }
11         int count = 0 ;    //当前值是第count小的数
12         int i = 0 ;        //nums1的下标 
13         int j = 0 ;        //nums2的下标 
14         int k = 0 ;       //res的下标
15         int min ;
16         /*
17          * 将两个有序数组进行排序的过程
18          * 当total为偶数时,结果为总数的第 (total-1)/2+1个数和第(total-1)/2+2个数
19          * 当total为基数时,结果为总数的第(total-1)/2+1个数
20          * 所以,当count > (total-1)/2 时,开始存储,直到res存满为止
21          */        
22         while((i < nums1.length ) && (j < nums2.length) && (k < res.length)){
23             count++ ;
24             min = nums1[i] > nums2[j] ? nums2[j++] : nums1[i++] ;      
25             if(count > (total-1)/2){
26                 res[k++] = min ;
27             }
28         }
29         //考虑nums2先排除完而没有完全得到需要的结果的情况
30         while((i < nums1.length ) && (k < res.length)){
31             count++ ;
32             min = nums1[i++] ;
33             if(count > (total-1)/2){
34                 res[k++] = min ;
35             }
36         }
37       //考虑nums1先排除完而没有完全得到需要的结果的情况
38         while((j < nums2.length ) && (k < res.length)){
39             count++ ;
40             min = nums2[j++] ;
41             if(count > (total-1)/2){
42                 res[k++] = min ;
43             }
44         }
45         
46         //返回结果
47         if(total%2 == 1){
48             return res[0] ;
49         }else{
50             return ((res[0] + res[1])/2.0) ;
51         }
52     }
53 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IMWeb前端团队

JavaScript强化教程——sort() 方法

本文作者:IMWeb 王军 原文出处:IMWeb社区 未经同意,禁止转载 本文为 H5EDU 机构官方 HTML5培训 教程,主要介绍:JavaScr...

2005
来自专栏机器学习实践二三事

python基础----map和reduce

map和reduce Map简单来说就是:一个映射函数就是对一些独立元素组成的概念上的列表的每一个元素进行指定的操作 Reduce简单来说就是:对一个列表的...

2056
来自专栏CodeSheep的技术分享

Java编程思想学习录(连载之:一切都是对象)

1698
来自专栏琦小虾的Binary

map 学习(下)——C++ 中的 hash_map, unordered_map

map 学习(下)——C++ 中的 hash_map, unordered_map 接上篇《map 学习(一)——C++中 map 的使用》。 一、hash_m...

3.1K7
来自专栏前端黑板报

ES6-arrows

从今天开始记录学习ES6的知识点,这次学习的是新增:Arrow functions Arrows以=>为简写形式,特点: 语法简洁 文法固定的this对象 总是...

2095
来自专栏技术换美食换不换

块状链表

的复杂度,而如果将整个块状链表维护成有序的,它甚至可以实现平衡树的一些操作[1],毕竟平衡树也可以看作是一种维护序列的方法。 又因为块状链表只在每个分块记录一...

1172
来自专栏老马说编程

(27) 剖析包装类 (中) / 计算机程序的思维逻辑

本节继续探讨包装类,主要介绍Integer类,下节介绍Character类,Long与Integer类似,就不再单独介绍了,其他类基本已经介绍完了,不再赘述。 ...

22310
来自专栏小L的魔法馆

第十四届浙江财经大学程序设计竞赛重现赛--A-A Sad Story

3077
来自专栏magicsoar

Effective Modern C++翻译(4)-条款3:了解decltype

条款3 了解decltype decltype是一个有趣的东西,给它一个变量名或是一个表达式,decltype会告诉你这个变量名或是这个表达式的类型,通常,告诉...

1989
来自专栏Petrichor的专栏

tensorflow编程: Variables

tf.moving_average_variables tf.global_variables_initializer tf.local_variabl...

1721

扫码关注云+社区

领取腾讯云代金券