Median of Two Sorted Arrays

url : Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 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)).

var findMedianSortedArrays = function(nums1, nums2) {
	var arr3 = [],
    		len1 = nums1.length,
    		len2 = nums2.length,
    		i = 0,
    		j = 0,
    		temp1,
    		temp2;
    	while( i < len1 && j < len2){
    		temp1 = nums1[i];
    		temp2 = nums2[j];
    		if(temp1 < temp2){
    			arr3.push(temp1);
    			i++;
    		}else{
    			arr3.push(temp2);
    			j++;
    		}
    	}
    	if(i < len1){
    		arr3 = arr3.concat(nums1.slice(i));
    	}
    	if(j < len2){
    		arr3 = arr3.concat(nums2.slice(j));
    	}
    	if(arr3.length % 2 === 0){
    		return (arr3[parseInt((arr3.length + 1)/2)] +
    		 arr3[parseInt((arr3.length - 1)/2)])/2;
	    	
    	}else{
    		return arr3[parseInt(arr3.length/2)];
    	}
};

时间复杂度不符合题意······先这么做吧。其实就是归并排序,然后取中值,数组是偶数的话,中间两个数的和/2
数组是奇数的话,就是 中间那个值。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据