LeetCode刷题日志#6:寻找两个有序数组的中位数
文章目录
题目:传送门
类别:数组
难度:困难
思路
题目简单易懂,思路也比较快想出来。既然是两个有序数组,那么不必将数组合并以及全量的遍历。
可以想象,面前放着两排数组,每次从他俩头部取一个较小的数。既然知道长度,那么取到第几个是中位数也是知道的。不难写出代码:
代码
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
const midIndex = (nums1.length + nums2.length) / 2;
let targetIndex1, targetIndex2;
if (midIndex === ~~midIndex) {
// 总数为偶数
targetIndex1 = midIndex;
targetIndex2 = midIndex + 1;
} else {
// 总数为奇数
targetIndex1 = ~~midIndex + 1;
}
let countedNum = 0;
while(true) {
const nextNum1 = nums1[0];
const nextNum2 = nums2[0];
if (nextNum1 === undefined) {
return getResultFromOneArr(targetIndex1, targetIndex2, countedNum, nums2);
}
if (nextNum2 === undefined) {
return getResultFromOneArr(targetIndex1, targetIndex2, countedNum, nums1);
}
countedNum += 1;
if (countedNum === targetIndex1) {
if (targetIndex2 === undefined) {
if (nextNum1 < nextNum2) {
return nextNum1;
} else {
return nextNum2;
}
} else {
let targetNum1, targetNum2;
// 寻找 targetNum1
if (nextNum1 < nextNum2) {
targetNum1 = nextNum1;
nums1.shift();
} else {
targetNum1 = nextNum2;
nums2.shift();
}
// 寻找 targetNum2
const targetNum2_nextNum1 = nums1[0];
const targetNum2_nextNum2 = nums2[0];
if (targetNum2_nextNum1 === undefined) {
targetNum2 = targetNum2_nextNum2;
} else if (targetNum2_nextNum2 === undefined){
targetNum2 = targetNum2_nextNum1;
} else {
targetNum2 = targetNum2_nextNum1 < targetNum2_nextNum2 ? targetNum2_nextNum1 : targetNum2_nextNum2;
}
return (targetNum1 + targetNum2) / 2;
}
}
if (nextNum1 < nextNum2) {
nums1.shift();
} else {
nums2.shift();
}
}
};
function getResultFromOneArr(targetIndex1, targetIndex2, countedNum, nums) {
if (targetIndex2 === undefined) {
const targetIndex = targetIndex1 - countedNum - 1;
return nums[targetIndex];
} else {
const targetIndex = targetIndex1 - countedNum - 1;
return (nums[targetIndex] + nums[targetIndex + 1]) / 2;
}
}
思考
以上代码复杂之处在于,对于两个条件的判断:
- 中位数是一个数,还是两个数(的平均值)?
- 当一个数组取完了怎么办?
看优秀题解有个取巧的方法,中位数如果是两个数(称为左数、右数),我们选择右数。如果根据上面挨个取数的方法,那么当我们取到右数的时候,前一个数就是左数了。所以,这题可以简化成,两个有序数组合并排序之后求指定下标的数。这样不要考虑复杂的边界条件了。
简化后的代码:
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
const midIndex = (nums1.length + nums2.length) / 2;
let needTwo, targetCountedNum;
if (midIndex === ~~midIndex) {
// 总数为偶数
needTwo = true;
targetCountedNum = midIndex + 1;
} else {
// 总数为奇数
needTwo = false;
targetCountedNum = ~~midIndex + 1;
}
let countedNum = 0;
let lastNum, currentNum;
while(true) {
const nextNum1 = nums1[0];
const nextNum2 = nums2[0];
lastNum = currentNum;
if (nextNum1 === undefined) {
currentNum = nums2.shift();
} else if (nextNum2 === undefined) {
currentNum = nums1.shift();
} else if (nextNum1 < nextNum2) {
currentNum = nums1.shift();
} else {
currentNum = nums2.shift();
}
countedNum += 1;
if (countedNum === targetCountedNum) {
if (needTwo) {
return (lastNum + currentNum) / 2;
} else {
return currentNum;
}
}
}
};
代码简化了,时空复杂度基本没变化。主要因为本质没有变化,还是挨个取。而且原来的算法有个优化:就是当一个数组取没了,直接算另一个数组的下标。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论