警告
本文最后更新于 2021-08-23，文中内容可能已过时。
题目链接
易知：
- 每行升序
- 每列升序
所以，我们可以对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
bool searchMatrix(vector<vector<int>> matrix, int target) {
auto row = upper_bound(matrix.begin(), matrix.end(), target, [](const int b, const vector<int> &a) {
return b < a[0];
});
if (row == matrix.begin()) {
return false;
}
--row;
return binary_search(row->begin(), row->end(), target);
}
};
|
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
| class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int rowIndex = binarySearchFirstColumn(matrix, target);
if (rowIndex < 0) {
return false;
}
return binarySearchRow(matrix[rowIndex], target);
}
public int binarySearchFirstColumn(int[][] matrix, int target) {
int low = -1, high = matrix.length - 1;
while (low < high) {
int mid = (high - low + 1) / 2 + low;
if (matrix[mid][0] <= target) {
low = mid;
} else {
high = mid - 1;
}
}
return low;
}
public boolean binarySearchRow(int[] row, int target) {
int low = 0, high = row.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (row[mid] == target) {
return true;
} else if (row[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return false;
}
}
|
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
| int binarySearchFirstColumn(int** matrix, int matrixSize, int target) {
int low = -1, high = matrixSize - 1;
while (low < high) {
int mid = (high - low + 1) / 2 + low;
if (matrix[mid][0] <= target) {
low = mid;
} else {
high = mid - 1;
}
}
return low;
}
bool binarySearchRow(int* row, int rowSize, int target) {
int low = 0, high = rowSize - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (row[mid] == target) {
return true;
} else if (row[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return false;
}
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
int rowIndex = binarySearchFirstColumn(matrix, matrixSize, target);
if (rowIndex < 0) {
return false;
}
return binarySearchRow(matrix[rowIndex], matrixColSize[rowIndex], target);
}
|
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
| var searchMatrix = function(matrix, target) {
const rowIndex = binarySearchFirstColumn(matrix, target);
if (rowIndex < 0) {
return false;
}
return binarySearchRow(matrix[rowIndex], target);
};
const binarySearchFirstColumn = (matrix, target) => {
let low = -1, high = matrix.length - 1;
while (low < high) {
const mid = Math.floor((high - low + 1) / 2) + low;
if (matrix[mid][0] <= target) {
low = mid;
} else {
high = mid - 1;
}
}
return low;
}
const binarySearchRow = (row, target) => {
let low = 0, high = row.length - 1;
while (low <= high) {
const mid = Math.floor((high - low) / 2) + low;
if (row[mid] == target) {
return true;
} else if (row[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return false;
}
|
1
2
3
4
5
6
7
8
| func searchMatrix(matrix [][]int, target int) bool {
row := sort.Search(len(matrix), func(i int) bool { return matrix[i][0] > target }) - 1
if row < 0 {
return false
}
col := sort.SearchInts(matrix[row], target)
return col < len(matrix[row]) && matrix[row][col] == target
}
|
- 时间复杂度：$ O(\log m + \log n)=O(\log mn) $
根据特性可将二维数组看作一维的升序数组，再使用二分搜索查找。（要求二维数组每行元素个数相等）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int low = 0, high = m * n - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
int x = matrix[mid / n][mid % n]; // 中位数映射到行和列
if (x < target) {
low = mid + 1;
} else if (x > target) {
high = mid - 1;
} else {
return true;
}
}
return false;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int low = 0, high = m * n - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
int x = matrix[mid / n][mid % n];
if (x < target) {
low = mid + 1;
} else if (x > target) {
high = mid - 1;
} else {
return true;
}
}
return false;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
int m = matrixSize, n = matrixColSize[0];
int low = 0, high = m * n - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
int x = matrix[mid / n][mid % n];
if (x < target) {
low = mid + 1;
} else if (x > target) {
high = mid - 1;
} else {
return true;
}
}
return false;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| var searchMatrix = function(matrix, target) {
const m = matrix.length, n = matrix[0].length;
let low = 0, high = m * n - 1;
while (low <= high) {
const mid = Math.floor((high - low) / 2) + low;
const x = matrix[Math.floor(mid / n)][mid % n];
if (x < target) {
low = mid + 1;
} else if (x > target) {
high = mid - 1;
} else {
return true;
}
}
return false;
};
|
1
2
3
4
5
| func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
i := sort.Search(m*n, func(i int) bool { return matrix[i/n][i%n] >= target })
return i < m*n && matrix[i/n][i%n] == target
}
|