共计 1974 个字符,预计需要花费 5 分钟才能阅读完成。
一、归并排序办法实现
// 工夫复杂度 O(m+n), 空间复杂度 O(m+n)
var findMedianSortedArrays = function(nums1, nums2) {let nums = [], m = nums1.length, n = nums2.length;
if(m === 0) { //nums1 为空数组
if(n % 2 === 0) { //nums2 的长度为偶数
return (nums2[n/2 - 1] + nums2[n/2])/2;
} else {return nums2[Math.floor(n/2)];
}
}
if(n === 0) { //nums2 为空数组
if(m % 2 === 0) { //nums1 的长度为偶数
return (nums1[m/2 - 1] + nums1[m/2])/2;
} else {return nums1[Math.floor(m/2)];
}
}
let count = 0, i = 0, j = 0; //count 代表合并后的数组的长度, i, j 别离代表遍历 nums1, nums2 的索引
while(count !== (m + n)) {if(i === m) { //nums1 曾经遍历实现
while(j !== n) {nums[count++] = nums2[j++];
}
break;
}
if(j === n) { //nums2 曾经遍历完
while(i !== m) {nums[count++] = nums1[i++];
}
break;
}
// 这样能够保障合并后的数组是有序的
if(nums1[i] < nums2[j]) {nums[count++] = nums1[i++];
} else {nums[count++] = nums2[j++];
}
}
if(count % 2 === 0) { // 合并后的数组的元素个数是偶数
return (nums[count/2 - 1] + nums[count/2])/2;
} else {return nums[Math.floor(count/2)];
}
};
console.log(findMedianSortedArrays([0, 1, 2, 2, 3], [3, 4, 5]));
二、数组连贯后排序实现
// 工夫复杂度 O(m+n), 空间复杂度 O(m+n)
var findMedianSortedArrays = function(nums1, nums2) {
let length1 = nums1.length;
let length2 = nums2.length;
let middle = (length1 + length2 - 1)/2;
var nums = nums1.concat(nums2).sort();
if(Math.floor(middle) === middle) { // 如果 middle 是一个整数
return nums[middle];
} else { // 如果 middle 不是一个整数
return (nums[Math.floor(middle)] + nums[Math.ceil(middle)])/2;
}
};
console.log(findMedianSortedArrays([0, 1, 2, 2, 3], [3, 4, 5]));
三、双指针法实现
// 工夫复杂度 O(m+n), 空间复杂度 O(1)
/**
* 双指针法:如果两个数组的和为偶数的话,则需遍历 len/2 + 1 次,如果为奇数,则需遍历 Math.floor(len/2) + 1 次,* 应用 prev 和 current 来别离记录上一轮循环和该轮循环的值
* @param {Array} nums1
* @param {Array} nums2
*/
var findMedianSortedArrays = function(nums1, nums2) {
let m = nums1.length, n = nums2.length, len = m + n;
let prev = -1, current = -1, aStart = 0, bStart = 0; //prev 保留上一轮循环的后果,current 保留以后循环的后果,aStart 示意 nums1 的指针,bStart 示意 nums2 的指针
for(let i = 0; i <= len/2; i++) {
prev = current; //prev 指向上一轮循环的值
//nums1 指针向后移的条件:aStart < m 且 nums1[aStart] < nums2[bStart],然而第二个条件的前提条件是 nums2 的指针不能越界
if(aStart < m && (bStart >= n || nums1[aStart] < nums2[bStart])) {current = nums1[aStart++];
} else {current = nums2[bStart++];
}
}
if(len % 2 === 0) {return (prev + current)/2;
} else {return current;}
};
console.log(findMedianSortedArrays([0, 1, 2, 3], [3, 4, 5]));
正文完
发表至: javascript
2020-09-10