題目描述

題目分析

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

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一無所知。雖然已經(jīng)學習了lambda表達式，但是不太能夠靈活運用。對于這種STL已經(jīng)實現(xiàn)了的算法，有些細節(jié)可能不同，我們需要傳遞一個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);} };

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

總結(jié)

以上是生活随笔為你收集整理的每日一题：leetcode74.搜索二维矩阵的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。