本文主要是介绍LeetCode-240. 搜索二维矩阵 II【数组 二分查找 分治 矩阵】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
LeetCode-240. 搜索二维矩阵 II【数组 二分查找 分治 矩阵】
- 题目描述:
- 解题思路一:从左下角或者右上角元素出发,来寻找target。
- 解题思路二:右上角元素,代码
- 解题思路三:暴力也能过
- 解题思路四:二分查找
题目描述:
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1:
输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出:true
示例 2:
输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出:false
提示:
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109
解题思路一:从左下角或者右上角元素出发,来寻找target。
如下图所示,我们将矩阵逆时针旋转 45° ,并将其转化为图形式,发现其类似于 二叉搜索树 ,即对于每个元素,其左分支元素更小、右分支元素更大。因此,通过从 “根节点” 开始搜索,遇到比 target 大的元素就向左,反之向右,即可找到目标值 target 。
“根节点” 对应的是矩阵的 “左下角” 和 “右上角” 元素,本文称之为 标志数 ,以 matrix 中的 左下角元素 为标志数 flag ,则有:
- 若 flag > target ,则 target 一定在 flag 所在 行的上方 ,即 flag 所在行可被消去。
- 若 flag < target ,则 target 一定在 flag 所在 列的右方 ,即 flag 所在列可被消去。
“右上角” 元素 也是类似
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:i, j = len(matrix) - 1, 0while i >= 0 and j < len(matrix[0]):if matrix[i][j] > target: i -= 1elif matrix[i][j] < target:j += 1else:return Truereturn False
时间复杂度:O(n+m)
空间复杂度:O(1)
解题思路二:右上角元素,代码
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:i, j = 0, len(matrix[0]) - 1while i < len(matrix) and j >= 0:if matrix[i][j] > target:j -= 1elif matrix[i][j] < target:i += 1else:return Truereturn False
时间复杂度:O(n+m)
空间复杂度:O(1)
解题思路三:暴力也能过
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:for row in matrix:for element in row:if element == target:return Truereturn False
时间复杂度:O(nm)
空间复杂度:O(1)
解题思路四:二分查找
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:for row in matrix:idx = bisect.bisect_left(row, target)if idx < len(row) and row[idx] == target:return Truereturn False
时间复杂度:O(mlogn)
空间复杂度:O(1)
这篇关于LeetCode-240. 搜索二维矩阵 II【数组 二分查找 分治 矩阵】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!