Median of Two Sorted Arrays, time complexity is O(min(m,n))


  • 0
    public class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        	if (nums1 == null || nums1 == null)
        		throw new NullPointerException();
        	int nums1L = nums1.length;
        	int nums2L = nums2.length;
        	int length = nums1L + nums2L;
        	//需要一个计数器来记录比较次数(需要比较length/2 )
        	int count = 0;
        	//指示两个数组的当前位置
        	int i = 0;
        	int j = 0;
        	//检查数组nums1和nums2为空的情况
        	if (nums1L < 1 && nums2L < 1)
        		return 0;
        	else if (nums1L < 1) {
        		//元素个数为奇数
        	    if (length == 1) return nums2[j];
        		if (length % 2 != 0) {
        			//如果数组1元素个数为0,从当前位置遍历数组2
        			while (j < nums2L) {
        				count++;
        				j++;
        				if (count == (length / 2)) return nums2[j];
        			}
        		} else {
        			//如果数组1元素个数为0,从当前位置遍历数组2
        			while (j < nums2L) {
        				count++;
        				j++;
        				if (count == (length / 2)) return ((double)nums2[j - 1] +nums2[j]) / 2;
        			}
        		}
        	} else if (nums2L < 1) {
        		if (length == 1) return nums1[i];
        		if (length % 2 != 0) {
        			//如果数组2元素个数为0,从当前位置遍历数组2
        			while (i < nums1L) {
        				count++;
        				i++;
        				if (count == (length / 2)) return nums1[i];
        			}
        		} else {
        			//如果数组2元素个数为0,从当前位置遍历数组1
        			while (i < nums1L) {
        				count++;
        				i++;
        				if (count == (length / 2)) return ((double)nums1[i - 1] +nums1[i]) / 2;
        			}
        		}
        		
        	}	
        	// 判断length是奇数还是偶数
        	//如果是奇数,则取中间的那一位
        	if (length % 2 != 0) {
        		//遍历这两个数组,有两种情况发生:1.在没到达边界前计算出中间位置;2.到达边界以后算出中间位置
        		while (i < nums1L && j < nums2L) {  			
        			//当count = length / 2时,到了中间的位置,获取它的值
        			count++;
        			if (nums1[i] < nums2[j]) {
        				i++;
        				if (count == (length / 2) && i < nums1L) {
        					if (nums1[i] < nums2[j]) 	  return nums1[i];
        				    else                     	  return nums2[j];
            			} else if (count == (length / 2) && i == nums1L) {
            				if (nums1[ i- 1] < nums2[j])  return nums2[j];
            				else 						  return nums1[ i - 1];
            			} else if (i == nums1L)			  break;
        			} else {
        				j++;
        				if (count == (length / 2) && j < nums2L) {
        					if (nums2[j] < nums1[i]) 	  return nums2[j];
        					else 					 	  return nums1[i];
            			} else if (count == (length / 2) && j == nums2L) {
            				if (nums2[ j - 1] < nums1[i]) return nums1[i];
            				else 						  return nums2[ j - 1];
            			} else if (j == nums2L)			  break;
        			} 			
        		}
        		//数组到达边界,分析是哪种情况:1.数组1到达边界;2.数组2到达边界
        		if (i == nums1L) {
        			//如果数组1越界,从当前位置遍历数组2
        			while (j < nums2L) {
        				count++;
        				j++;
        				if (count == (length / 2)) return nums2[j];
        			}
        		} else if (j == nums2L) {
        			//如果数组2越界,从当前位置遍历数组1
        			while (i < nums1L) {
        				count++;
        				i++;
        				if (count == (length / 2)) return nums1[i];
        			}
        		}	
        	} else {
        		//否则取中间两位的平均
        		//遍历这两个数组,有两种情况发生:1.在没到达边界前计算出中间位置;2.到达边界以后算出中间位置
        		while (i < nums1L && j < nums2L) {  			
        			//当count = length / 2时,到了中间的位置,获取它的值
        			count++;
        			if (nums1[i] < nums2[j]) {
        				i++;
        				if (count == (length / 2) && i < nums1L) {
        					if (nums1[i] < nums2[j]) {
        						return ((double)nums1[i - 1] +nums1[i]) / 2;
        					}
        				    else {
        				    	return ((double)nums2[j] + nums1[i - 1]) / 2; 
        				    }
            			} else if (count == (length / 2) && i == nums1L) {
            				return ((double)nums1[i - 1] +nums2[j]) / 2;
            			} else if (i == nums1L)			  break;
        			} else {
        				j++;
        				if (count == (length / 2) && j < nums2L) {
        					if (nums2[j] < nums1[i]) {
        						return ((double)nums2[j - 1] +nums2[j]) / 2;
        					}
        				    else {
        				    	return ((double)nums1[i] + nums2[j - 1]) / 2; 
        				    }
            			} else if (count == (length / 2) && j == nums2L) {
            				return ((double)nums2[j - 1] +nums1[i]) / 2;
            			} else if (j == nums2L)			  break;
        			}	
        		}
        		//数组到达边界,分析是哪种情况:1.数组1到达边界;2.数组2到达边界
        		if (i == nums1L) {
        			//如果数组1越界,从当前位置遍历数组2
        			while (j < nums2L) {
        				count++;
        				j++;
        				if (count == (length / 2)) return ((double)nums2[j] + nums2[j - 1]) / 2; 
        			}
        		} else if (j == nums2L) {
        			//如果数组2越界,从当前位置遍历数组1
        			while (i < nums1L) {
        				count++;
        				i++;
        				if (count == (length / 2)) return ((double)nums1[i] + nums1[i - 1]) / 2;
        			}
        		}
        	}
        	return 0;    
        }
    }
    

    Advantage : Time complexity is O(min(m,n))
    Disadvantage : Code is complicated


  • 0

    @龙卫兵 效率高的原因是:利用两个指针来只是这两个数组,通过比较当前两个数组值的大小来移动指针,以其中一个指针到达终点为结束标志。


  • 0

    @龙卫兵 sorry,时间复杂度我不怎么会计算,如果说错了,多担待


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.