李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
LeetCode-4 寻找两个有序数组的中位数
Leefs
2020-02-19 AM
1359℃
0条
# LeetCode-4 寻找两个有序数组的中位数 题目描述 ``` 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 ``` 示例 1: > nums1 = [1, 3] > nums2 = [2] 则中位数是 2.0 示例 2: > nums1 = [1, 2] > nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5 **代码实现** ```java public class Solution04 { public static void main(String[] args) { int[] arr1={1,5}; int[] arr2={3}; double v = findMedianSortedArrays(arr1, arr2); System.out.println(v); } public static double findMedianSortedArrays(int[] nums1, int[] nums2) { int len = nums1.length + nums2.length; double Median = 0; int i = 0; int count = 0; int a = 0;//指向nums1数组的角标 int b = 0; //指向nums2数组的角标 int[] num3 = new int[len];//用来存放有序的 nums1数组和mums2数组 while (i < len) { if (a < nums1.length && b < nums2.length) { //两数组都未遍历完,相互比较后加入 if (nums1[a] > nums2[b]) { num3[i] = nums2[b]; b++; count++; } else { num3[i] = nums1[a]; a++; count++; } } else if (a < nums1.length) { //num2已经遍历完,无需比较,直接将剩余num1加入 num3[i] = nums1[a]; a++; count++; } else if (b < nums2.length) { //num1已经遍历完,无需比较,直接将剩余num2加入 num3[i] = nums2[b]; b++; count++; } if(count == len /2 +1 ) break;//找到中间+1位置后停止查找 i++; } if(len % 2 == 0){ double d1 = num3[i]; double d2 = num3[i-1]; Median = (d1 + d2)/2; } else{ Median = num3[i]; } return Median; } } ``` > 运行结果 ``` 3.0 ```
标签:
LeetCode刷题
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://lilinchao.com/archives/632.html
上一篇
【转载】volatile关键字简介
下一篇
【转载】单例模式简介
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
43
标签云
Beego
Typora
算法
工具
持有对象
MyBatisX
JavaScript
Hbase
Git
Eclipse
数学
前端
Jenkins
SpringCloud
FileBeat
Netty
MySQL
队列
Map
哈希表
二叉树
JVM
Livy
人工智能
并发线程
LeetCode刷题
Stream流
容器深入研究
Spark Core
机器学习
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞