英文:
Is there a way to binary search a column of a 2D std::vector without creating a new vector?
问题
在解决 Leetcode 74: Search a 2D Matrix 的 C++20 问题,其中需要在部分有序(按行主序)的二维矩阵中搜索元素。
该解决方案找到目标可能存在的行,并在该行中进行搜索。
为此,它对行的最后一个元素进行二进制搜索,寻找具有最后一个元素大于等于目标的第一行。
有没有办法使用 std::lower_bound
在不创建右侧列作为 std::vector
的情况下搜索最右侧的列?
[示例]
#include <iostream>
#include <ranges>
#include <algorithm>
#include <vector>
auto searchMatrix(auto&& matrix, auto target) {
// 或许使用一个迭代器?
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
,但某些概念未得到满足。
英文:
I am solving Leetcode 74: Search a 2D Matrix in C++20 in which a partially ordered (in row-major) 2D matrix is to be searched for an element.
The solution finds a row in which the target must reside, if at all, and searches in that row.
To do that, it binary-searches on the rows' last elements, looking for the first row with a last element greater equal to the target.
Is there a way to use std::lower_bound
to search the rightmost column, without creating the rightmost column as a std::vector
?
[Example]
#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;
}
I tried using a view
, but certain concepts were not satisified.
答案1
得分: 2
可以使用 [`views::transform`](https://en.cppreference.com/w/cpp/ranges/transform_view) 来创建一个由每个 `vector` 的最后一个元素组成的视图:
auto searchMatrix(auto&& matrix, auto target) {
auto rightmost_col =
matrix | std::views::transform([](const auto& inner) -> const auto& {
return inner.back();
});
// ...
}
[演示](https://godbolt.org/z/7119vY6bP)
或者你可以直接在 `matrix | std::views::join` 上进行二分查找(只需一行)
auto searchMatrix(auto&& matrix, auto target) {
return std::ranges::binary_search(matrix | std::views::join, target);
}
[演示](https://godbolt.org/z/jcEGMzaqT)
英文:
You can use views::transform
to create a view consisting of the last element of each vector
:
auto searchMatrix(auto&& matrix, auto target) {
auto rightmost_col =
matrix | std::views::transform([](const auto& inner) -> const auto& {
return inner.back();
});
// ...
}
Or you can do a binary search directly on matrix | std::views::join
(with only one line)
auto searchMatrix(auto&& matrix, auto target) {
return std::ranges::binary_search(matrix | std::views::join, target);
}
答案2
得分: 1
类似在C++20中使用范围很赞(如果使用得当):
class Solution {
public:
bool searchMatrix(const std::vector<std::vector<int>>& matrix, int target)
{
using namespace std::ranges;
return binary_search(views::join(matrix), target);
}
};
英文:
ranges in C++20 rocks (if used properly):
class Solution {
public:
bool searchMatrix(const std::vector<std::vector<int>>& matrix, int target)
{
using namespace std::ranges;
return binary_search(views::join(matrix), target);
}
};
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论