网站建设与设计 毕业设计,青田建设局网站,怎么对页面颜色进行设计,设计英语题目描述 题目分析
感觉这是一个放错标签的简单题。题目非常简单#xff0c;思路应该很明确是二分#xff0c;我很快写了一个#xff08;虽然不小心把!打成调试了一会#xff09;。
class Solution {
public:bool searchMatrix(vectorvectorint mat…题目描述 题目分析
感觉这是一个放错标签的简单题。题目非常简单思路应该很明确是二分我很快写了一个虽然不小心把!打成调试了一会。
class Solution {
public:bool searchMatrix(vectorvectorint 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:pairbool, int row_lower_bound(vectorvectorint 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(vectorvectorint matrix, int target) {auto row upper_bound(matrix.begin(), matrix.end(), target, [](const int b, const vectorint 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)而前者的可拓展性高一些
