LeetCode 74. Search a 2D Matrix

LeetCode 74. Search a 2D Matrix

Description:

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:

    Consider the following matrix:
    [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
    ]
    Given target = 3, return true.


分析:

由于每一行每一列都有序,可以直接把二维数组转化为有序的一维数组,在有序数组中查找target即可。
下面代码查找target只是用了遍历,效率不够高,可以利用二分搜索算法来求解,效率会高一点。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
vector<int> temp;
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[i].size(); j++) {
temp.push_back(matrix[i][j]);
}
}
for (int i = 0; i < temp.size(); i++) {
if (target == temp[i]) return true;
}
return false;

}
};
------本文结束感谢阅读------