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

相关文章

来自专栏算法修养

回文树总结

最近学习了回文树,这个比较新颖的数据结构,相应的写了12道关于回文树的题目。所以总结一下。 网络上关于回文树的学习的博客有很多质量很好的,这里就不具体分析回文树...

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

P1418 选点问题

题目描述 给出n个点,m条边,每个点能控制与其相连的所有的边,要求选出一些点,使得这些点能控制所有的边,并且点数最少。同时,任意一条边不能被两个点控制 输入输出...

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

洛谷P3224 [HNOI2012]永无乡

题目描述 永无乡包含 n 座岛,编号从 1 到 n,每座岛都有自己的独一无二的重要度,按照重要度可 以将这 n 座岛排名,名次用 1 到 n 来表示。某些岛之间...

2635
来自专栏算法channel

机器学习|海量数据求top K 之最小堆实现

01 — 要求 从海量数据中按照某个规则找出前K名,简化起见,从一个海量的整形数组中,找出前K个最大元素。 无法直接一次性读入内存,可以将文件依次分批读入,找出...

3266
来自专栏小二的折腾日记

LeetCode-56and57-Merge-Intervals

如例子中所示,每个数组的前后分别表示开始和结束,工作是合并有重叠的数组。例如,由于[1,3]和[2,6]有重叠,故直接改为[1,6]后输出。 想法还是比较简单的...

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

Burnside引理与Polya定理

感觉这两个东西好鬼畜= = ,考场上出了肯定不会qwq。不过还是学一下吧用来装逼也是极好的

461
来自专栏Bingo的深度学习杂货店

Q27 Remove Element

Given an array and a value, remove all instances of that value in-place and retu...

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

PTA 邻接矩阵存储图的深度优先遍历

6-1 邻接矩阵存储图的深度优先遍历(20 分) 试实现邻接矩阵存储图的深度优先遍历。 函数接口定义: void DFS( MGraph Graph, Vert...

1916
来自专栏趣学算法

数据结构 第13讲 三元组 (F、C、L/R) 序列创建二叉树

/* 输入三元组 (F、C、L/R) 序列输入一棵二叉树的诸边(其中 F 表示双亲结点的标识,C 表示孩子结点标识,L/R...

853
来自专栏desperate633

LeetCode LintCode和大于S的最小子数组Minimum Size Subarray Sum题目分析

给定一个由 n 个整数组成的数组和一个正整数 s ,请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解,则返回 -1。

712

扫码关注云+社区