[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 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1192
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

1K4
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2608
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2349
来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1876
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

6436
来自专栏一个会写诗的程序员的博客

java.sql.SQLException: connection holder is null

java.sql.SQLException: connection holder is null

1481
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1442
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2782
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

832

扫码关注云+社区