一般网站建设,企业门户网站建设公司,网站开发技术主管工作职责,重庆网站建设公司的网站LeetCode-240. 搜索二维矩阵 II【数组 二分查找 分治 矩阵】 题目描述#xff1a;解题思路一#xff1a;从左下角或者右上角元素出发#xff0c;来寻找target。解题思路二#xff1a;右上角元素#xff0c;代码解题思路三#xff1a;暴力也能过解题思路四#xff1a;二分… 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(nm) 空间复杂度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(nm) 空间复杂度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)
