首页 > 代码库 > [leetcode] Search a 2D Matrix
[leetcode] Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]]
Given target = 3, return true.
https://oj.leetcode.com/problems/search-a-2d-matrix/
二分法。
1. 先二分在第一列（或者第一行）找出元素可能在的行，然后二分查找该列。
2. 二维数组转为一维数组，然后利用 /，%求坐标二分查找。
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; int m = matrix.length; int n = matrix[0].length; int left = 0, right = m - 1; int mid; while (left <= right) { mid = (left + right) / 2; if (target > matrix[mid][0]) { left = mid + 1; } else if (target < matrix[mid][0]) right = mid - 1; else { return true; } } int row = right; if (row < 0 || row >= m) return false; // not found, keep searching left = 0; right = n - 1; while (left <= right) { mid = (left + right) / 2; if (target > matrix[row][mid]) left = mid + 1; else if (target < matrix[row][mid]) right = mid - 1; else return true; } return false; } public boolean searchMatrix2(int[][] matrix, int target) { if (matrix.length == 0 || matrix[0].length == 0) { return false; } int xLength = matrix[0].length; int min = 0; int max = matrix[0].length * matrix.length - 1; int x, y, cur; while (min <= max) { cur = (min + max) / 2; y = cur / xLength; x = cur % xLength; if (matrix[y][x] == target) { return true; } else if (target < matrix[y][x]) { max = cur - 1; } else { min = cur + 1; } } return false; } public static void main(String[] args) { int[][] matrix = new int[][] { { 1, 3, 5, 7 }, { 10, 11, 16, 20 }, { 23, 30, 34, 50 } }; System.out.println(new Solution().searchMatrix(matrix, 7)); System.out.println(new Solution().searchMatrix2(matrix, 7)); }}
扩展：如果说不保证每行第一个数据比上一行最后一个大，只满足比同列上面行的数据大，该如何处理。
即
Table[i][j] ≤ Table[i][j + 1],
Table[i][j] ≤ Table[i + 1][j]
则，此时上述2分法不起作用了，leetcode论坛里这个题目的讨论讲的很详细，列举了很多错误的解法和正确的解法，看这里。
随便举个反例，下面的矩阵找9或者找10。
{ 1, 4, 7, 9, 15 },
{ 2, 5, 8, 12, 19 },
{ 3, 6, 10, 16, 22 },
{ 10, 13, 14, 17, 24 },
{ 18, 21, 23, 26, 30 }
里面最好的两种解法。假设m==n方便讨论。
思路1：从右上角（或者左下角）开始，行列两个指针，如果当前元素比target小，向下移动行指针；如果当前元素比target大，向左移动列指针，直到找到元素或者失败。最坏情况移动对角线长度，复杂度O(n)。
思路2：优化的二分查找。每次在中间行（或者列）二分查到找所在范围，如果没查到继续查找左下和右上两个小矩阵（左上和右下不可能存在）。 T(n)=2T(n/2)+clogn。根据主定律可求出复杂度也是O(n)。
思路1代码：
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; int m=matrix.length; int n=matrix[0].length; int i=0; int j=n-1; while(i<m&&j>=0){ if(target<matrix[i][j]){ j--; } else if(target > matrix[i][j]){ i++; } else return true; } return false; }}
思路2代码：（有空写）