KK's blog

每天积累多一些

0%

LeetCode 074 Search a 2D Matrix

Posted on Edited on Disqus:

LeetCode



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.

Example 1:



Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true


Example 2:



Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false


Constraints:

m == matrix.length n == matrix[i].length
1 <= m, n <= 100 -10<sup>4</sup> <= matrix[i][j], target <= 10<sup>4</sup>

题目大意：

矩阵中每一行有序，下一行的首元素大于上一行的尾元素。求target是否在矩阵中

列+行搜索解题思路：

先对列做二分搜索，再对行

LeetCode 074 Search a 2D Matrix 每一行有序，下一行的首元素大于上一行的尾元素 + 找target
LeetCode 240 Search a 2D Matrix II 按行按列有序 + 找target
LeetCode 378 Kth Smallest Element in a Sorted Matrix 按行按列有序 + 找第k大
矩阵结构方面，第一道每一行都是独立，所以可以独立地按行按列做二分法
后两道，矩阵二维连续，所以解法都是类BFS，从某个点开始，然后比较它相邻的两个点。出发点不同，第二道在近似矩阵中点(右上角或左下角)，第三道在左上角出发。

解题步骤：

N/A

注意事项：

  1. Python代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    	col = [matrix[i][0] for i in range(len(matrix))]
    	row_idx = bisect.bisect(col, target) - 1
    	if row_idx < 0 or row_idx >= len(matrix):
    		return False
    	if matrix[row_idx][0] == target:
    		return True
    	col_idx = bisect.bisect(matrix[row_idx], target) - 1
    	if col_idx < 0 or col_idx >= len(matrix[0]):
    		return False
    	return True if matrix[row_idx][col_idx] == target else False

算法分析：

时间复杂度为O(logn + logm)，空间复杂度O(n), 可以写一个二分法来做列搜索，这样空间为常量。

全矩阵搜索算法II解题思路：

对矩阵的左上，右下元素作为start, end得到mid转化成(i, j)找到矩阵位置。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean searchMatrix(int[][] matrix, int target) {
	if (matrix.length==0)
		return false;
	int lo = 0;
	int hi = matrix.length*matrix[0].length - 1;
	while (lo <= hi) {
		// Key is in a[lo..hi] or not present.
		int mid = lo + (hi - lo) / 2;
		int x = mid/matrix[0].length;
		int y = mid%matrix[0].length;
		if (target < matrix[x][y])
			hi = mid - 1;
		else if (target > matrix[x][y])
			lo = mid + 1;
		else
			return true;
	}
	return false;
}

算法分析：

时间复杂度为O(logn + logm)，空间复杂度O(1)。

Free mock interview