leetcode-74-Search-a-2D-Matrix

TOREVIEW

描述


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:

1
2
3
4
5
6
7
8
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

1
2
3
4
5
6
7
8
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false

分析


方法有很多,最优的时间复杂度是 $O(log(M)+log(N)), 也就是两次二分实现,因为题目中有要求下一行的第一个元素总是大于上一行的最后一个元素。

解决方案1(Python)


暴力的方法。

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
for values in matrix:
if target in values:
return True
return False

解决方案2(Python)


利用右上角的元素进行比较,如果当前元素大于 target, 那么目标值一定不在最后一列,如果当前元素小于 target, 那么目标值一定不在第一行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if not matrix or not matrix[0]:
return False
rows = len(matrix)
cols = len(matrix[0])
row, col = 0, cols - 1
while True:
if row < rows and col >= 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
col -= 1
else:
row += 1
else:
return False

解决方案3(Golang)


跟 解决方案2 思路一样,用 Golang 解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func searchMatrix(matrix [][]int, target int) bool {
row, col := 0, len(matrix[0])-1

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

解决方案4(Golang)


二分法解决。不知道为什么这代码会过不了测试,在本地跑没有问题。提交记录 https://leetcode.com/submissions/detail/568683969/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func searchMatrix(matrix [][]int, target int) bool {
row, col := 0, len(matrix[0])

up, down := 0, row-1
nowRow := -1
for up < down {
mid := (up+down) / 2
if matrix[mid][0] > target {
down = mid - 1
} else if matrix[mid][col-1] < target {
up = mid + 1
} else {
nowRow = mid
break
}
}

if nowRow == -1 {
nowRow = up
}
left, right := 0, col-1
for left <= right {
mid := (left+right) / 2
if matrix[nowRow][mid] == target {
return true
} else if matrix[nowRow][mid] > target {
right = mid - 1
} else {
left = mid + 1
}
}
return false
}

相关问题


题目来源