高效搜索二维矩阵的三种解法
LeetCode240编写一个高效的算法来搜索mxn矩阵matrix中的一个目标值target。该矩阵具有以下特性每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例输入matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target 5输出truePython解法1.直接查找class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) - bool: for i in range(len(matrix)): for j in range(len(matrix[0])): if matrix[i][j] target: return True return False2.二分查找class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) - bool: for row in matrix: if self.res(row, target): return True return False def res(self, row:List[int], target: int) - bool: l, r 0, len(row)-1 while l r: mid (l r) // 2 if row[mid] target: return True elif row[mid] target: l mid 1 else: r mid - 1 return False3.对角查找只适用此题class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) - bool: if not matrix or not matrix[0]: return False n, m len(matrix), len(matrix[0]) x, y 0, m - 1 #选右上角元素 while x n and y 0: if matrix[x][y] target: return True elif matrix[x][y] target: y - 1 else: x 1 return False右上角元素有独一无二的性质左边所有元素 当前值下边所有元素 当前值同理也可以选左下角这里不做演示Java解法1.二分查找class Solution { public boolean searchMatrix(int[][] matrix, int target) { for(int[] row: matrix){ if (res(row, target)){ return true; } } return false; } private boolean res(int[] row, int target){ int l 0; int r row.length - 1; int mid 0; while(l r){ mid (l r) / 2; if(row[mid] target){ return true; }else if(row[mid] target){ l mid 1; }else{ r mid - 1; } } return false; } }2.对角查找只适用此题class Solution { public boolean searchMatrix(int[][] matrix, int target) { int n matrix.length; int m matrix[0].length; int x 0; int y m - 1; while(x n y 0){ if(matrix[x][y] target){ return true; }else if(matrix[x][y] target){ x; }else{ y--; } } return false; } }C解法1.二分查找class Solution { public: bool searchMatrix(vectorvectorint matrix, int target) { // 判空 if (matrix.empty() || matrix[0].empty()) return false; for (auto row : matrix) { int l 0, r row.size() - 1; while (l r) { int mid l (r - l) / 2; // 防溢出 if (row[mid] target) { return true; } else if (row[mid] target) { l mid 1; } else { r mid - 1; } } } return false; } };2.对角查找只适用此题class Solution { public: bool searchMatrix(vectorvectorint matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; int m matrix.size(); int n matrix[0].size(); int x 0, y n - 1; // 右上角起点 while (x m y 0) { int cur matrix[x][y]; if (cur target) { return true; } else if (cur target) { y--; // 当前列全部更大左移一列 } else { x; // 当前行全部更小下移一行 } } return false; } };
