共计 2490 个字符,预计需要花费 7 分钟才能阅读完成。
题目:算法(leetode,附思维导图 + 全副解法)300 题之(4)寻找两个正序数组的中位数
一 题目形容
二 解法总览(思维导图)
三 全副解法
1 计划 1
1) 代码:
var findMedianSortedArrays = function(nums1, nums2) {// 留神: push() 返回的是该数组的最新长度,// 所以不能够 nums1.push(...nums2).sort((a, b) => a - b);
nums1.push(...nums2);
nums1.sort((a, b) => a - b);
let l = nums1.length;
// 判断奇偶性,返回对应的中位数
return l % 2 ? nums1[parseInt(l / 2)] : (nums1[l / 2 - 1] + nums1[l / 2]) / 2;
};
2 计划 2
1) 代码:
var findMedianSortedArrays = function(nums1, nums2) {
let n1 = nums1.length;
let n2 = nums2.length;
// 两个数组总长度
let len = n1 + n2;
// 保留以后挪动的指针的值 (在 nums1 或 nums2 挪动),和上一个值
let preValue = -1;
let curValue = -1;
// 两个指针别离在 nums1 和 nums2 上挪动
let point1 = 0;
let point2 = 0;
// 须要遍历 len/ 2 次,当 len 是奇数时,最初取 curValue 的值,是偶数时,最初取 (preValue + curValue)/ 2 的值
for (let i = 0; i <= Math.floor(len/2); i++) {
preValue = curValue;
// 须要在 nums1 上挪动 point1 指针
if (point1 < n1 && (point2 >= n2 || nums1[point1] < nums2[point2])) {curValue = nums1[point1];
point1++;
} else {curValue = nums2[point2];
point2++;
}
}
return len % 2 === 0
? (preValue + curValue) / 2
: curValue
};
3 计划 3
1) 代码:
var findMedianSortedArrays = function(nums1, nums2) {
// nums1 长度比 nums2 小
if (nums1.length > nums2.length) {[nums1, nums2] = [nums2, nums1];
}
let m = nums1.length;
let n = nums2.length;
// 在 0~m 中查找
let left = 0;
let right = m;
// median1:前一部分的最大值
// median2:后一部分的最小值
let median1 = 0;
let median2 = 0;
while(left <= right) {// 前一部分蕴含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
// 后一部分蕴含 nums1[i .. m-1] 和 nums2[j .. n-1]
const i = left + Math.floor((right - left) / 2);
const j = Math.floor((m + n + 1) / 2) - i;
const maxLeft1 = i === 0 ? -Infinity : nums1[i - 1];
const minRight1 = i === m ? Infinity : nums1[i];
const maxLeft2 = j === 0 ? -Infinity : nums2[j - 1];
const minRight2 = j === n ? Infinity : nums2[j];
if (maxLeft1 <= minRight2) {median1 = Math.max(maxLeft1, maxLeft2);
median2 = Math.min(minRight1, minRight2);
left = i + 1;
} else{right = i - 1;}
}
return (m + n) % 2 == 0 ? (median1 + median2) / 2 : median1;
};
四 更多
1 刷题进度
1)LeetCode:307 / 2390。2)《剑指 offer》:66 / 66。3)相干学习材料与笔记汇总:https://github.com/CYBYOB/algorithm-leetcode/tree/master/ 材料 %26 笔记。4)注:所有题目均有 2- 5 种 左右的解法,后续还将不断更新题目 & 题解。敬请期待~
也欢送大家进群一起 学习、交换、刷题 & 拿高薪~
2 GitHub – LeetCode 我的项目仓库
0)本我的项目地址:https://github.com/CYBYOB/algorithm-leetcode。指标、愿景:让每个人都能领有肯定的算法能力、以应答面试中(会触类旁通的同学还能够将其融入本人的肌肉和血液,甚至可能赋能于公司的业务和技术)的算法。1)我的项目的根目录下的 README.md 文件,能够帮您疾速查阅每 1 道题的起源、难度、所有的题解计划等。2)而每个题解(即 index.md 文件)中,还将附带题目形容、所有的题解计划的思维导图(.xmind 文件)、思路和技巧等。3)每种题解计划都有具体的正文,通过“数字步骤”将形象的算法逻辑、清晰和有档次的展现于您的背后。能够说是,开箱即用~
4)所有的题解计划都是通过作者 1 人之手,故代码格调及其对立。一旦浏览达到一定量后,后续将大大晋升您的浏览速度 ——“正所谓、质变引起量变”。5)自己每周仍在一直的更新 —— 保障每周都有新的题目、题解计划刺激着您的神经 和 刷题欲望。欢送对算法感兴趣的同学退出咱们的社群。QQ 群:933919972;作者 QQ:1520112971;作者 VX:c13227839870(可拉您进群、一起学习与交换~)。
3 作者标签
1)“BAT 里 1 名小小的伪全栈工程师,主攻前端,偶然写点后端”。2)2019 年的微信小程序利用开发赛 - 全国三等奖;2019CODA 较量 - 前 17/211 强 且 荣获“优良团队”名称 等。3)“半自媒体人”,在校期间、集体公众号(IT 三少。新自媒体(公众号)号:码农三少)在半年内实现了 0 到 5.8K+ 的粉丝增长等。
正文完