題目描述

題目分析

感覺這是一個放錯標簽的簡單題。題目非常簡單，思路應該很明確是二分，我很快寫了一個（雖然不小心把!=打成==調試了一會）。

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {if (target < matrix[0][0] || target > matrix.back().back()) return false;auto result = row_lower_bound(matrix, 0, matrix.size(), target);if (result.first) {int x = result.second;const auto &vec = matrix[x];return  lower_bound(vec.cbegin(), vec.cend(), target) != upper_bound(vec.cbegin(), vec.cend(), target);} else {return false;}}
private:pair<bool, int> row_lower_bound(vector<vector<int>> &matrix, int l, int r, int target) {;while (l < r) {int mid = (l + r) >> 1;if (target >= matrix[mid][0] && target <= matrix[mid].back()) return {true, mid};else if (target < matrix[mid][0]) r = mid;else l = mid + 1;}return {false, 0};}
};

但是當我看到題解的時候我覺得我對STL一無所知。雖然已經學習了lambda表達式，但是不太能夠靈活運用。對于這種STL已經實現了的算法，有些細節可能不同，我們需要傳遞一個lambda表達式定制一下操作就可以了。

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);}
};

題解還有另一種解法，是把二維數組看成一維的，雖然思路很好，但是復雜度應該是沒什么變化的。一個是O(n)+O(m)，一個是O(nm)，而前者的可拓展性高一些