我正在用C++20求解Leetcode 74: Search a 2D Matrix,其中一个偏序(以行为主)2D矩阵将被搜索一个元素。
解决方案将查找目标必须驻留的行(如果存在),并在该行中进行搜索。
为此,它对行的最后一个元素进行二进制搜索,查找最后一个元素大于等于目标的第一行。
有没有一种方法可以使用std::lower_bound
搜索最右边的列,而不用将最右边的列创建为std::vector
?
[示例]
#include <iostream>
#include <ranges>
#include <algorithm>
#include <vector>
auto searchMatrix(auto&& matrix, auto target) {
// MAYBE use an iterator?
auto rightmost_col = [&]{
using Col = std::remove_reference<decltype(matrix[0])>::type;
auto rightmost_col = Col();
for (auto i : std::views::iota(0, std::ssize(matrix))) {
rightmost_col.push_back(matrix[i].back());
}
return rightmost_col;
}();
auto find = [&](const auto& space) -> std::optional<decltype(target)> {
auto pos = std::ranges::lower_bound(space, target);
if (pos == std::ranges::end(space)) return std::nullopt;
return pos - std::ranges::begin(space);
};
if (auto candidate_row = find(rightmost_col)) {
if (auto candidate_col = find(matrix[*candidate_row])) {
return matrix[*candidate_row][*candidate_col] == target;
}
}
return false;
}
auto main([[maybe_unused]] int argc, [[maybe_unused]] char** argv) -> int {
auto matrix = std::vector<std::vector<int>>{{1,3,5,7}, {10,11,16,20}, {23,30,34,60}};
auto target = 3;
auto result = searchMatrix(matrix, target);
std::cout << std::boolalpha << result << std::endl;
}
我尝试使用view
,但某些概念并不令人满意。
2条答案
按热度按时间eagi6jfj1#
可以使用
views::transform
创建一个视图,该视图由每个vector
的最后一个元素组成:Demo
或者您可以直接在
matrix | std::views::join
上进行二进制搜索(只有一行)Demo
iklwldmw2#
范围在C++20岩石(如果使用得当):
https://godbolt.org/z/GhGWaWebh