0%

[Leetcode]74. Search a 2D Matrix(C++)

题目描述

题目链接:74. Search a 2D Matrix

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.

例子

例子 1

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

例子 2

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

Constraints

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

解题思路

由于矩阵每一行都是有序的,且每一行都比上一行大,因此思路很明确,可以使用两次二分查找,第一次找到有可能包含目标元素的行(首元素比目标值小,且下一行首元素比目标值大),第二次在该行查找该元素即可,代码如下:

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
34
35
36
37
38
#include <vector>

class Solution {
public:
bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();

int left = 0;
int right = m - 1;
while (left < right) {
int mid = (left + right) / 2 + 1;
if (matrix[mid][0] > target) {
right = mid - 1;
} else if (matrix[mid][0] < target) {
left = mid;
} else {
return true;
}
}

int row = left;
left = 0;
right = n - 1;
while (left < right) {
int mid = (left + right) / 2;
if (matrix[row][mid] > target) {
right = mid - 1;
} else if (matrix[row][mid] < target) {
left = mid + 1;
} else {
return true;
}
}

return matrix[row][left] == target;
}
};
  • 时间复杂度: O(log max(m,n))
  • 空间复杂度: O(1)

GitHub 代码同步地址: 74.SearchA2DMatrix.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions