Leetcode 搜索一个二维矩阵:这个矩阵的特点是,对于任意的 x = matrix[i,j], 左上部分(红色)的值均小于 x, 右下部分(青色)的值均大于 x,而左下、右上部分(灰色)和 x 的大小关系则完全未知。
所以一个简单的思路即从矩阵右上角或者左下角开始,逐渐向对角方向(并不一定严格对角)走,并不断排除所在位置左上、右下部分从而达到比较高的效率。时间复杂度为 O(m+n)
代码如下:
- public boolean searchMatrix(int[][] matrix, int target) {
- int r = matrix.length;
- if (r < 1) return false;
- int c = matrix[0].length;
- int i = 0,
- j = c - 1;
- while (i < r && j >= 0) {
- if (matrix[i][j] == target) return true;
- else if (matrix[i][j] < target) i++;
- else j--;
- }
- return false;
- }
python 代码如下:
- class Solution: #@param {
- integer[][]
- }
- matrix#@param {
- integer
- }
- target#@
- return {
- boolean
- }
- def searchMatrix(self, matrix, target) : y = len(matrix[0]) - 1
- for x in range(len(matrix)) : while y and matrix[x][y] > target: y -= 1
- if matrix[x][y] == target: return True
- return False
另外一种思路即 tag 中提到的二分查找和分治的思想,每次取矩阵中心 x,然后将矩阵分割为左上、左下、右上、右下四个部分,如何 target 大于 x, 则舍弃左上部分,如果小于 x , 则舍弃右下部分。
时间复杂度
java 代码如下:
- public class Solution {
- public boolean searchMatrix(int[][] matrix, int target) {
- int r = matrix.length;
- if (r < 1) return false;
- int c = matrix[0].length;
- return helpFunc(0, 0, r - 1, c - 1, matrix, target);
- } //divide the matrix into 4 parts and then recursive call //start point and end point private Boolean helpFunc(int sx, int sy, int ex, int ey, int[][]m, int t){ if(t < m[sx][sy] || t > m[ex][ey]) return false; if(sx < ex || sy < ey){ //middle point int mx = (ex-sx)/2+sx; int my = (ey-sy)/2+sy; boolean ret = false; if(my < ey) ret = ret || helpFunc(sx,my+1,mx,ey,m,t); if(mx < ex) ret = ret || helpFunc(mx+1,sy,ex,my,m,t); if(m[mx][my] > t) return helpFunc(sx,sy,mx,my,m,t)||ret; else if(m[mx][my]
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: