二、剑指 Offer 04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
第一个方法坐标轴法
题解思路： 在这个二维数组里面，数组的排列顺序的每一行大小是→递增，每一列是↓递增。那么我们要在这个数组里面找到这个数字，我们就得利用这个规律。那么随机假设数组中的一个值的位置关系就是，上边，左边的数值比他小，右边，下边的数值比他大。那我们就可以把要找的数值带入二维数组中的一个中间大小的值a，进行比较。要找的数值比a大，那么就往下走或者往右走(递增方向)。要找的数值比a小，那么就往上走或者往左走(递减方向)。但是既然递增或者递减方向有2种走法，但是我们应该一条路走到黑，不然一会往这，一会往那自然不容易找到。这就乱了套了。
那我们就找右上角或者左下角的数组中的中间大小的数值为起点。就选右上方吧，叫这个数值为a，叫要找到数值叫target。判断target与a的大小，比a大就往下走，比a小就往左走。直到周边这个句子的边界“碰墙”了还要往外走就证明数值target没有在这数值里面了。
// 哈希表 选的右上角 var findNumberIn2DArray = function(matrix, target) { if (! matrix.length) return false; let i = 0; let j = matrix[0].length-1; while(i < matrix.length && j >= 0 ) { if (matrix[i][j] > target) { // 向左边查找 j--; } else if (matrix[i][j] < target) { // 向下边查找 i++; } else { return true; } } return false; }; // 选的左下角 var findNumberIn2DArray = function(matrix, target) { if (! matrix.length) return false; let i = matrix.length - 1; let j = 0; while(j < matrix[0].length && i >= 0 ) { if (matrix[i][j] > target) { i--; } else if (matrix[i][j] < target) { j++; } else { return true; } } return false; }; 复制代码
第二个方法暴力循环遍历
题解思路： 遍历这个二维数组，一个一个比较。
// 改变原数组循环遍历 var findNumberIn2DArray = function(matrix, target) { for (let i = 0; i < matrix.length; i++) { for (let j = 0; j < matrix[0].length; j++) { if (matrix[i][j] === target) return true; } } return false; }; 复制代码
第三个方法二分法
题解思路： 这里运用了二分法，如果不懂二分法就得先了解一下二分法的使用。二分法最常用就是在一个递增或者递减的一维数组中寻找一个数值。那么这道题的二维数组也只不过是多个一维数组嵌套的。我们就可以使用一个循环，把二维数组中的每一个一维数组取出来进行二分法查找，找不到就取下一个一维数组二分查找。
我们要解决的问题有：
①循环取出一维数组。
②在每一个一维数组中使用二分查找
var findNumberIn2DArray = function(matrix, target) { for(const nums of matrix){ // 这里的nums就是一维数组 let left = 0, right = nums.length - 1; while(left <= right){ const mid = Math.floor((right - left) / 2) + left; if(nums[mid] === target){ return true; }else if(nums[mid] > target){ right = mid - 1; }else{ left = mid + 1; } } } return false; }; 复制代码
如果看不懂上面的 for(const nums of matrix)，那么可以老是使用for循环，遍历代表一维数组楼层的i。只不过在表示左右left，right指针的时候得书写matrix[i]表示楼层。
var findNumberIn2DArray = function(matrix, target) { for(let i = 0; i < matrix.length; i++){ let left = 0, right = matrix[i].length - 1; while(left <= right){ const mid = Math.floor((right - left) / 2) + left; if( matrix[i][mid] === target){ return true; }else if( matrix[i][mid] > target){ right = mid - 1; }else{ left = mid + 1; } } } return false; }; 复制代码
二分法升级版本
其实就是再每次进行二分法查找的前面加一个判断，如果这个一层的一维数组的第一个数比target大，那么就根本不需要使用二分法查找的必要了（这一层的一维数组全部的值都比target大），直接循环条到下一阶段。
var findNumberIn2DArray = function(matrix, target) { for(let i = matrix.length - 1; i >= 0; i--){ if (matrix[i][0] <= target) { let left = 0, right = matrix[i].length - 1; while(left <= right){ const mid = Math.floor((right - left) / 2) + left; if( matrix[i][mid] === target){ return true; }else if( matrix[i][mid] > target){ right = mid - 1; }else{ left = mid + 1; } } } } return false; }; 复制代码
第四个方法数组降维
题解思路： 把二维数组降维到一维数组，然后查找target（也就图一乐这方法）
var findNumberIn2DArray = function(matrix, target) { return matrix.flat(Infinity).includes(target) }; 复制代码
var findNumberIn2DArray = function(matrix, target) { if(!matrix.length) return false let arr = matrix.reduce((a,b) => { return a.concat(b) }) return arr.includes(target) };
