0%

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

题目描述

题目链接:240. Search a 2D Matrix II

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The 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.

例子

例子 1

Input: 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
Output: true

例子 2

Input: 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
Output: false

Follow Up

Note

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -10^9 <= matix[i][j] <= 10^9
  • All the integers in each row are sorted in ascending order.
  • All the integers in each column are sorted in ascending order.
  • -10^9 <= target <= 10^9

解题思路

[Leetcode]74. Search a 2D Matrix(C++) 的变种版本,这次给定矩阵符合条件是,每一行同样是已排序,但每一行不一定所有元素都比上一行大,只满足每一列是升序。也就是我们在上一题中用过的二分查找锁定某一行的方法不可行了,因为可能有多行满足第一个元素比target 小,最后一个元素比 target 大的条件。因此我们需要对每一行进行一次二分查找,不过可以利用每一列也是升序的特点,对每行行首和行尾分别进行一次二分查找,筛掉所有元素都大于/小于 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <vector>

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

std::pair<int, int> valid_range{0, m - 1};

int left = 0;
int right = m - 1;
// filter out rows where all elements are larger than target
while (left < right) {
int mid = (left + right) / 2 + 1;
if (matrix[mid][0] > target) {
right = mid - 1;
valid_range.second = right;
} else if (matrix[mid][0] < target) {
left = mid;
} else {
return true;
}
}

// filter out rows where all elements are smaller than target
left = 0;
while (left < right) {
int mid = (left + right) / 2;
if (matrix[mid][n - 1] < target) {
left = mid + 1;
valid_range.first = left;
} else if (matrix[mid][n - 1] > target) {
right = mid;
} else {
return true;
}
}

// for the rest rows, do a binary search for each row
for (int r = valid_range.first; r <= valid_range.second; ++r) {
left = 0;
right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (matrix[r][mid] < target) {
left = mid + 1;
} else if (matrix[r][mid] > target) {
right = mid - 1;
} else {
return true;
}
}
}

return false;
}
};
  • 时间复杂度: O(mlog n) — 由于有剪枝,实际复杂度会更小一点
  • 空间复杂度: O(1)

GitHub 代码同步地址: 240.SearchA2DMatrixIi.cpp

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