排序矩阵查找
分治
-
解题思路：
![]( "排序矩阵查找（分治）")
- 使用分治法，先比较目标与矩阵对角线元素，找到元素返回 true，找不到则分解；
- 步骤一 分解：矩阵被划分成 4个 子问题：可以看到绿色部分一定小于目标元素；红色部分一定大于目标元素；只需在剩下的两个行列升序的矩阵中寻找目标元素；
- 步骤二 子问题分别求解：子问题元素个数为 0 或者最小元素大于目标返回 false；否则对两个子矩阵继续递归分解；
- 步骤三 合并： 任一子矩阵内寻找到目标元素，则返回 true；
-
复杂度：
- 时间复杂度：O((m+n)*log(m+n))；从矩阵左上方开始不断比较目标值与对角线元素，寻找划分位置；如果未找到目标值，接着继续在两个子矩阵重复这个过程（递归）；
- 空间复杂度：O(log(m+n))；需常数级临时变量；递归调用占用额外空间，递归深度为log(m+n)；
-
代码实现：
var searchMatrix = function (matrix, target) { let row = matrix.length; if (row === 0) return false; let col = matrix[0].length; if (col === 0) return false; return searchSubMatrix(matrix, target, 0, 0, row - 1, col - 1); }; function searchSubMatrix(matrix, target, startRow, startColumn, endRow, endColumn) { // 1.结束条件： // 元素个数小于1 // 矩阵最小元素大于目标值（所有元素都大于目标值） if (startRow > endRow || startColumn > endColumn || matrix[startRow][startColumn] > target) return false; // 对角线元素个数 let diagonalLen = Math.min(endRow - startRow + 1, endColumn - startColumn + 1); // 在对角线上查找元素、分解问题、递归求解、合并 for (let i = 0; i < diagonalLen; i++) { if (matrix[startRow + i][startColumn + i] === target) return true; // 当找到对角线最后 或者 下一个对角线的值大于 target if (i === diagonalLen - 1 || matrix[startRow + i + 1][startColumn + i + 1] > target) { // 找到了分界点，寻找 4 个区域中的剩下两个（右上、左下） return searchSubMatrix(matrix, target, startRow, startColumn + i + 1, startRow + i, endColumn) || searchSubMatrix(matrix, target, startRow + i + 1, startColumn, endRow, startColumn + i); } } return false; }
双指针
-
解题思路：
![]( "排序矩阵查找（双指针）")
- 从矩阵右上方元素开始，比较当前元素与目标值的大小；
- 若当前元素等于目标值，那么返回 true；
- 若当前元素小于目标值，那么当前元素左侧的元素都会小于目标值，指针下移；
- 若当前元素大于目标值，那么当前元素右下方的元素都会大于目标值，指针左移；
- 若指针在矩阵外，返回 false；
-
复杂度：
- 时间复杂度：O(m+n)，最多比较 m+n-1 次；
- 空间复杂度：O(1)，空间消耗方面只需常数级临时变量；
-
代码实现：
var searchMatrix = function (matrix, target) { let row = matrix.length; if (row === 0) return false; let col = matrix[0].length; if (col === 0) return false; // 初始位置为右上角的元素 let currentRow = 0, currentColumn = col - 1; while (currentColumn >= 0 && currentRow < row) { // 当前元素等于target if (matrix[currentRow][currentColumn] === target) return true; if (matrix[currentRow][currentColumn] < target) { // 当前元素小于target，指针下移 currentRow++; } else { // 当前元素大于target，指针左移 currentColumn--; } } return false; };
打赏作者
您的打赏是我前进的动力
微信
支付宝
761.特殊的二进制序列
上一篇
评论
