Is there a way to binary search a column of a 2D std::vector without creating a new vector?

huangapple
go评论87阅读模式
英文:

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 的情况下搜索最右侧的列？

[示例]

  1. #include <iostream>
  2. #include <ranges>
  3. #include <algorithm>
  4. #include <vector>
  6. auto searchMatrix(auto&& matrix, auto target) {
  7.   // 或许使用一个迭代器？
  8.   auto rightmost_col = [&]{
  9.     using Col = std::remove_reference<decltype(matrix[0])>::type;
  10.     auto rightmost_col = Col();
  11.     for (auto i : std::views::iota(0, std::ssize(matrix))) {
  12.       rightmost_col.push_back(matrix[i].back());
  13.     }
  14.     return rightmost_col;
  15.   }();
  17.   auto find = [&](const auto& space) -> std::optional<decltype(target)> {
  18.     auto pos = std::ranges::lower_bound(space, target);
  19.     if (pos == std::ranges::end(space)) return std::nullopt;
  20.     return pos - std::ranges::begin(space);
  21.   };
  23.   if (auto candidate_row = find(rightmost_col)) {
  24.     if (auto candidate_col = find(matrix[*candidate_row])) {
  25.       return matrix[*candidate_row][*candidate_col] == target;
  26.     }
  27.   }
  28.   return false;
  29. }
  31. auto main([[maybe_unused]] int argc, [[maybe_unused]] char** argv) -> int {
  32.   auto matrix = std::vector<std::vector<int>>{{1,3,5,7}, {10,11,16,20}, {23,30,34,60}};
  33.   auto target = 3;
  34.   auto result = searchMatrix(matrix, target);
  35.   std::cout << std::boolalpha << result << std::endl;
  36. }

我尝试使用了一个 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]

  1. #include &lt;iostream&gt;
  2. #include &lt;ranges&gt;
  3. #include &lt;algorithm&gt;
  4. #include &lt;vector&gt;
  6. auto searchMatrix(auto&amp;&amp; matrix, auto target) {
  7.   // MAYBE use an iterator?
  8.   auto rightmost_col = [&amp;]{
  9.     using Col = std::remove_reference&lt;decltype(matrix[0])&gt;::type;
  10.     auto rightmost_col = Col();
  11.     for (auto i : std::views::iota(0, std::ssize(matrix))) {
  12.       rightmost_col.push_back(matrix[i].back());
  13.     }
  14.     return rightmost_col;
  15.   }();
  17.   auto find = [&amp;](const auto&amp; space) -&gt; std::optional&lt;decltype(target)&gt; {
  18.     auto pos = std::ranges::lower_bound(space, target);
  19.     if (pos == std::ranges::end(space)) return std::nullopt;
  20.     return pos - std::ranges::begin(space);
  21.   };
  23.   if (auto candidate_row = find(rightmost_col)) {
  24.     if (auto candidate_col = find(matrix[*candidate_row])) {
  25.       return matrix[*candidate_row][*candidate_col] == target;
  26.     }
  27.   }
  28.   return false;
  29. }
  31. auto main([[maybe_unused]] int argc, [[maybe_unused]] char** argv) -&gt; int {
  32.   auto matrix = std::vector&lt;std::vector&lt;int&gt;&gt;{{1,3,5,7}, {10,11,16,20}, {23,30,34,60}};
  33.   auto target = 3;
  34.   auto result = searchMatrix(matrix, target);
  35.   std::cout &lt;&lt; std::boolalpha &lt;&lt; result &lt;&lt; std::endl;
  36. }

I tried using a view, but certain concepts were not satisified.

答案1

得分: 2

  1. 可以使用 [`views::transform`](https://en.cppreference.com/w/cpp/ranges/transform_view) 来创建一个由每个 `vector` 的最后一个元素组成的视图：
  3.     auto searchMatrix(auto&& matrix, auto target) {
  4.       auto rightmost_col = 
  5.         matrix | std::views::transform([](const auto& inner) -> const auto& {
  6.                    return inner.back();
  7.                  });
  8.       // ...
  9.     }
  11. [演示](https://godbolt.org/z/7119vY6bP)
  13. 或者你可以直接在 `matrix | std::views::join` 上进行二分查找（只需一行）
  15.     auto searchMatrix(auto&& matrix, auto target) {
  16.       return std::ranges::binary_search(matrix | std::views::join, target);
  17.     }
  19. [演示](https://godbolt.org/z/jcEGMzaqT)
英文:

You can use views::transform to create a view consisting of the last element of each vector:

  1. auto searchMatrix(auto&amp;&amp; matrix, auto target) {
  2.   auto rightmost_col = 
  3.     matrix | std::views::transform([](const auto&amp; inner) -&gt; const auto&amp; {
  4.                return inner.back();
  5.              });
  6.   // ...
  7. }

Demo

Or you can do a binary search directly on matrix | std::views::join (with only one line)

  1. auto searchMatrix(auto&amp;&amp; matrix, auto target) {
  2.   return std::ranges::binary_search(matrix | std::views::join, target);
  3. }

Demo

答案2

得分: 1

类似在C++20中使用范围很赞（如果使用得当）：

  1. class Solution {
  2. public:
  3.     bool searchMatrix(const std::vector<std::vector<int>>& matrix, int target)
  4.     {
  5.         using namespace std::ranges;
  6.         return binary_search(views::join(matrix), target);
  7.     }
  8. };
英文:

ranges in C++20 rocks (if used properly):

  1. class Solution {
  2. public:
  3.     bool searchMatrix(const std::vector&lt;std::vector&lt;int&gt;&gt;&amp; matrix, int target)
  4.     {
  5.         using namespace std::ranges;
  6.         return binary_search(views::join(matrix), target);
  7.     }
  8. };

https://godbolt.org/z/GhGWaWebh

huangapple
  • 本文由 发表于 2023年3月3日 21:53:31
  • 转载请务必保留本文链接：https://go.coder-hub.com/75627951.html
  • binary-search
  • c++
  • c++20
  • iterator
  • stdvector
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定