LeetCode 074 Search a 2D Matrix

LeetCode

<div>

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:

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

Example 2:

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

Constraints:

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

</div>

题目大意：

矩阵中每一行有序，下一行的首元素大于上一行的尾元素。求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

注意事项：

Python代码：

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代码：

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)。