O(nlogn)实现
题目描述
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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,Consider the following 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]
]Given target = 5, return true.
Given target = 20, return false.
算法分析
题目要求为在一个二维矩阵中查找一个数，找到则返回true，否则返回false。
遇到查找的问题，我首先想到的是使用二分法。但是由于题目中的矩阵，虽然每一行每一列都是有序的，但是无法确定matrix[i+1][j]和matrix[i][j+1]的大小关系，因此，考虑对这个二维矩阵拆分为两层一维，并分别使用二分法。首先，用一次二分法确定行的范围：1
2
3
4
5
6
7
8
9
10
11
12while (up <= down) {
int mid = (up + down) / 2;
if (target < matrix[mid][0]) {
down = mid - 1;
}
else if (target > matrix[mid][0]) {
up = mid + 1;
}
else {
return true;
}
}
之后得到的down即为行的下限，之后对第0行到第down行分别进行二分查找，即可得到答案。每一行的二分查找同理：1
2
3
4
5
6
7
8
9
10
11
12
13int left = 0, right = matrix[0].size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target < matrix[r][mid]) {
right = mid - 1;
}
else if (target > matrix[r][mid]) {
left = mid + 1;
}
else {
return true;
}
}
代码实现
总体代码实现如下：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
36bool searchMatrix(vector<vector<int>>& matrix, int target) {
// 先二分查找出行的下限
int up = 0, down = matrix.size() - 1;
if (matrix.empty() || matrix[0].empty()) {
return false;
}
while (up <= down) {
int mid = (up + down) / 2;
if (target < matrix[mid][0]) {
down = mid - 1;
}
else if (target > matrix[mid][0]) {
up = mid + 1;
}
else {
return true;
}
}
// 再次使用二分法在筛选出的每一行查找目标
for (int r = 0; r <= down; r++) {
int left = 0, right = matrix[0].size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target < matrix[r][mid]) {
right = mid - 1;
}
else if (target > matrix[r][mid]) {
left = mid + 1;
}
else {
return true;
}
}
}
return false;
}
时间复杂度为O(nlogn)，效率一般。
O(n)实现
算法分析
再换一种思路，从这个矩阵本身的特点出发。对于任意一个数matrix[i][j]，难以对周围的数进行分割。但是对于两个特别的位置，matrix[n-1][0]和matrix[0][n-1]，如果用target和它们进行比较，是可以明确的排除掉某一行或这一列的。按照这个思路，假设从矩阵的左下角matrix[n-1][0]出发，先排除掉一行或者一列，再与剩余的matrix[n-2][0]或者matrix[n-1][1]比较，又可以去掉一行或一列，依次类推。
代码实现
实现如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty()) {
return false;
}
int row = matrix.size() - 1, col = matrix[0].size() - 1;
int r = row, c = 0;
while (r >= 0 && c <= col) {
if (target < matrix[r][c]) {
r--;
}
else if (target > matrix[r][c]) {
c++;
}
else {
return true;
}
}
return false;
}
这种看似简单粗暴的策略，时间复杂度不难得到，为O(n)，还要优于二分的算法。
注意：
- 由于题目输入包含空矩阵，所以无论哪一种方法，都要注意判断，防止越界。
- 二分法不同实现的边界要确定。
本文为博主原创文章，转载请注明出处。