LeetCode 74. 搜索二维矩阵

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 74. 搜索二维矩阵

思路分析

这个问题的关键是矩阵具有升序的性质：每行从左到右升序排列，每列从上到下升序排列。

参考代码

func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}

	// 从右上角开始
	row, col := 0, len(matrix[0])-1

	for row < len(matrix) && col >= 0 {
		if matrix[row][col] == target {
			return true
		} else if matrix[row][col] > target {
			col--
		} else {
			row++
		}
	}

	return false
}

时间复杂度：O(m + n)，其中 m 是矩阵的行数，n 是矩阵的列数。

空间复杂度：O(1)，只使用常数级别的额外空间。

func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}

	m, n := len(matrix), len(matrix[0])
	left, right := 0, m*n-1

	for left <= right {
		mid := left + (right-left)/2
		row := mid / n // 计算对应的行
		col := mid % n // 计算对应的列

		if matrix[row][col] == target {
			return true
		} else if matrix[row][col] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return false
}

时间复杂度：O(log(m * n))，其中 m 是矩阵的行数，n 是矩阵的列数。

空间复杂度：O(1)，只使用常数级别的额外空间。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/30863730