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

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

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 &lt;iostream&gt;
#include &lt;ranges&gt;
#include &lt;algorithm&gt;
#include &lt;vector&gt;

auto searchMatrix(auto&amp;&amp; matrix, auto target) {
  // MAYBE use an iterator?
  auto rightmost_col = [&amp;]{
    using Col = std::remove_reference&lt;decltype(matrix[0])&gt;::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 = [&amp;](const auto&amp; space) -&gt; std::optional&lt;decltype(target)&gt; {
    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) -&gt; int {
  auto matrix = std::vector&lt;std::vector&lt;int&gt;&gt;{{1,3,5,7}, {10,11,16,20}, {23,30,34,60}};
  auto target = 3;
  auto result = searchMatrix(matrix, target);
  std::cout &lt;&lt; std::boolalpha &lt;&lt; result &lt;&lt; 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&amp;&amp; matrix, auto target) {
  auto rightmost_col = 
    matrix | std::views::transform([](const auto&amp; inner) -&gt; const auto&amp; {
               return inner.back();
             });
  // ...
}

Demo

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

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

Demo

答案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&lt;std::vector&lt;int&gt;&gt;&amp; matrix, int target)
    {
        using namespace std::ranges;
        return binary_search(views::join(matrix), target);
    }
};

https://godbolt.org/z/GhGWaWebh

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

发表评论

匿名网友

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

确定