240、搜索二维矩阵|240、搜索二维矩阵 II | 算法（leetcode，附思维导图 + 全部解法）300题 240、搜索二维矩阵II|算法（l

零标题：算法（leetcode，附思维导图 + 全部解法）300题之（240）搜索二维矩阵 II 一题目描述
文章图片

文章图片

文章图片

二解法总览（思维导图）
文章图片

三全部解法面试官：题目看得差不多了吧，怎么样、有无思路呀？

狂徒张三：涉及“映射、数量、重复性（即去重）、唯一性（即次数）等”，我可能会优先考虑hash（JS里对应的是 map数据结构）。

面试官：那你先讲讲大致思路吧

【240、搜索二维矩阵|240、搜索二维矩阵 II | 算法（leetcode，附思维导图 + 全部解法）300题】狂徒张三：

1）遍历二维数组里的每个元素，将它们放在哈希表里。 2）最后判断 target 值，是否在哈希表里即可~

面试官：嗯嗯，整体思路是ok的，那么开始写吧

狂徒张三：过了2分52秒后，张三就写完了程序

1 方案1 1)代码：

// 方案1 “自己。哈希法”。 // 注：通过 124 / 129，会超时。 // 用时：15：14 - 15：16。 // 技巧：涉及“映射、数量、重复性（即去重）、唯一性（即次数）等”可优先考虑hash（JS里对应的是 map数据结构）。// 思路： // 1）状态初始化：m = matrix.length, n = matrix[0].length; // resMap = new Map(); // 2）遍历二维数组，将每个元素放入 resMap 中。 // 3）返回结果： resMap.has(target) 。 var searchMatrix = function(matrix, target) { // 1）状态初始化：m = matrix.length, n = matrix[0].length; // resMap = new Map(); const m = matrix.length, n = matrix[0].length; let resMap = new Map(); // 2）遍历二维数组，将每个元素放入 resMap 中。 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { const tempVal = matrix[i][j]; resMap.set(tempVal, 1); } }// 3）返回结果： resMap.has(target) 。 return resMap.has(target); };

旁边：代码在后台运行中，过了3秒，屏幕突然【闪现】出【通过 124 / 129，超出时间限制】。
面试官（面带一丝轻蔑）：小伙子，写代码要讲武德、要善于利用题干的条件

狂徒张三（定睛细看题干60秒后）：嗯嗯，有序，emmmm ---> 是否可以使用二分查找呢？

面试官：你仔细想想哈

狂徒张三（脑离回想二分查找的各种思路、模板后）：整体思路如下：

1）遍历二维数组的每一行，对每一行（即有序数组）使用二分查找 —— 判断 target 是否在里面。 2）若每一行都不存在 target 值，则返回 false ，否则返回 true 。

面试官：

240、搜索二维矩阵|240、搜索二维矩阵 II | 算法（leetcode，附思维导图 + 全部解法）300题

文章图片

旁白：几分钟不到，张三就写完了 “二分查找”法的代码并通过了所有的case。
2 方案2 1)代码：

// 方案2 “自己。二分查找”。 // 用时：15：37 - 15：43。 // 技巧：在有序的数组里进行元素的查找，可优先考虑“二分查找”。// 思路： // 1）状态初始化：m = matrix.length, n = matrix[0].length; // resFlag = false; 。 // 2）核心：遍历二维数组的每一行，对每一行（即有序数组）使用二分查找 —— 判断 target 是否在里面。 // 2.1）若 target 在当前行 —— isFindTarget(matrix[i], target)， // 则 resFlag = true 并退出搜索。 // 3）返回结果： resFlag 。 var searchMatrix = function(matrix, target) { const isFindTarget = (list = [], target = 0) => { const l = list.length; let left = 0, right = l - 1, resFlag = false; while (left <= right) { const mid = left + Math.floor((right - left) / 2), midVal = list[mid]; if (midVal === target) { resFlag = true; break; } else if (midVal > target) { right = mid - 1; } else { left = mid + 1; } }return resFlag; }; // 1）状态初始化：m = matrix.length, n = matrix[0].length; // resFlag = false; 。 const m = matrix.length, n = matrix[0].length; let resFlag = false; // 2）核心：遍历二维数组的每一行，对每一行（即有序数组）使用二分查找 —— 判断 target 是否在里面。 for (let i = 0; i < m; i++) { // 2.1）若 target 在当前行 —— isFindTarget(matrix[i], target)， // 则 resFlag = true 并退出搜索。 if (isFindTarget(matrix[i], target)) { resFlag = true; break; } }// 3）返回结果： resFlag 。 return resFlag; }

面试官：仔细看题干 —— “每行的元素从左到右升序排列。每列的元素从上到下升序排列。”，那么我们是否从一些特殊的位置开始搜索呢？

狂徒张三（仔细看了看）：嗯嗯，看起来左下角、右上角是比较靠中间的元素，我们可以从它们开始搜索。

面试官：

文章图片

狂徒张三：

比如， 1）我们从左下角开始不断【向上、向右】搜索。 1.1）若当前值 tempVal === target，则退出搜索。 1.2）若当前值 tempVal < target，则向右搜索。 1.3）若当前值 tempVal > target，则向上搜索。

面试官：

文章图片

3 方案3 1)代码：

// 方案3 “自己。Z 字形查找”。 // 用时：15：22 - 15：27。// 想法： // 1）题干中，“每行的元素从左到右升序排列。每列的元素从上到下升序排列。”。 // 2）那么我们开始选择较为中间的位置开始搜索，若当前值偏小就向右搜索、偏大就向上搜索、相等就退出搜索。// 思路： // 1）状态初始化：m = matrix.length, n = matrix[0].length; // i = m - 1, j = 0【从左下角开始搜索】, resFlag = true; // 2）核心：从左下角开始不断【向上、向右】搜索。 // 2.1）若当前值 tempVal === target，则退出搜索。 // 2.2）若当前值 tempVal < target，则向右搜索。 // 2.2）若当前值 tempVal > target，则向上搜索。// 3）返回结果 resFlag 。 var searchMatrix = function(matrix, target) { // 1）状态初始化：m = matrix.length, n = matrix[0].length; // i = m - 1, j = 0【从左下角开始搜索】, resFlag = true; const m = matrix.length, n = matrix[0].length; let i = m - 1, j = 0, resFlag = true; // 2）核心：从左下角开始不断【向上、向右】搜索。 while (true) { if (i < 0 || i >= m || j < 0 || j >= n) { resFlag = false; break; }const tempVal = matrix[i][j]; // 2.1）若当前值 tempVal === target，则退出搜索。 if (tempVal === target) { break; } // 2.2）若当前值 tempVal < target，则向右搜索。 else if (tempVal < target) { j++; } // 2.2）若当前值 tempVal > target，则向上搜索。 else { i--; } }// 3）返回结果 resFlag 。 return resFlag; };

旁白：张三写完了如上代码，急忙问面试官。

狂徒张三：通过面试了吧？

面试官：