[LeetCode] 4.Median of Two Sorted Arrays

题目:There are two sorted arrays nums1 andnums2 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.若为偶数,则为中间两个数的和除以2

个人提交的解法如下:首先算出两个数组的长度和和中位数的index,然后两个数组分别有两个指针,找到指定的位置即可。

思路比较简单,可是要考虑到边界情况,代码如下:

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
	        double ans = 0;
	        int totalLength=nums1.length+nums2.length;
	        boolean odd=false;
	        if(totalLength%2!=0)
	        	odd=true;
	        int midIndex=totalLength/2;       
	        int count=0;
	        int i=0,j=0;
	        while(i<nums1.length&&j<nums2.length){
	        	int flag;//用于判断当前是哪个数组的指针移动
	        	if(nums1[i]<=nums2[j]){
	        		flag=1;
	        		i++;
	        	}
	        	else {
	        		j++;
	        		flag=2;
	        	}       	
	        	if((!odd&&(count==midIndex-1)||(count==midIndex))){
	        		if(flag==1)ans+=nums1[i-1];
	        		else ans+=nums2[j-1];
	        		if(count==midIndex)//index已经为中位数,则直接返回
	        			if(odd) return ans;
	        			else return ans/2;
	        	}
	        	count++;
	        }
	      if(odd&&ans!=0)//奇数并且前面已经找到了一个数直接返回
	    	  return ans;
	      if(odd&&ans==0){//否则在剩下的数组里面找一个数
	    	  if(i==nums1.length)
	    		  return nums2[midIndex-i];
	    	  else
	    		  return nums1[midIndex-j];
	      }
	      if(ans==0){//若为偶数的情况且前面一个中位数都没找到
	    	  if(i==nums1.length)
	    		  return (double)(nums2[midIndex-i-1]+nums2[midIndex-i])/2;
	    	  else
	    		  return (double)(nums1[midIndex-j-1]+nums1[midIndex-j])/2;
	      }
	      else{//为偶数且找到了一个中位数
	    	  if(i==nums1.length)
	    		  return (double)(nums2[midIndex-i]+ans)/2;
	    	  else
	    		  return (double)(nums1[midIndex-j]+ans)/2;
	      }
	   }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏眯眯眼猫头鹰的小树杈

leetcode295. Find Median from Data Stream

这里采用了两个优先队列来实现。一个优先队列用来存储字符流中较小的一半,另一个用来存储字符流中数值较大的一半。这样当需要获取当前中位数时,就可以根据当前的数值个数...

1113
来自专栏数据结构与算法

P1141 01迷宫

题目描述 有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上,那么你可以移动到相邻4格中的某一格1上,同样若你位于一格1上,那么你可以移动到相邻4格中的某...

3456
来自专栏互联网杂技

前端面试中的常见的算法问题

虽说我们很多时候前端很少有机会接触到算法。大多都交互性的操作,然而从各大公司面试来看,算法依旧是考察的一方面。实际上学习数据结构与算法对于工程师去理解和分析问题...

3427
来自专栏小詹同学

Leetcode打卡 | No.016 最接近的三数之和

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

1284
来自专栏智能算法

前端面试中的常见的算法问题

作者:Jack Pu 链接:www.jackpu.com/qian-duan-mian-shi-zhong-de-chang-jian-de-suan-fa-w...

4348
来自专栏老马说编程

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

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

20310
来自专栏小樱的经验随笔

深入理解树状数组

树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之...

2567
来自专栏人工智能LeadAI

算法 | 排序算法图形化比较:快速排序、插入排序、选择排序、冒泡排序

用Objective-C实现几种基本的排序算法,并把排序的过程图形化显示。其实算法还是挺有趣的 。 选择排序 冒泡排序 插入排序 快速排序 01 选择排序 以升...

2927
来自专栏用户画像

7.4.2 选择排序之堆排序

堆排序是一个树形选择排序方法,它的特点是:在排序过程中,将L[1...n]看成是一棵完全二叉树的顺序存储结构,

554
来自专栏程序员互动联盟

【编程基础】零基础学习Java之运算符

学习计算机编程语言都会遇到运算符这一知识点,运算符这个知识点是教怎么运用编程语言进行最基本的数据处理,下面就讲一下在Java语言中运算符是怎么回事。 1、算术运...

33310

扫码关注云+社区