c++ 是否有方法在不创建新向量的情况下对2D std::vector的列进行二进制搜索?

yhxst69z  于 2023-03-05  发布在  其他
关注(0)|答案(2)|浏览(103)

我正在用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,但某些概念并不令人满意。

eagi6jfj

eagi6jfj1#

可以使用views::transform创建一个视图,该视图由每个vector的最后一个元素组成:

auto searchMatrix(auto&& matrix, auto target) {
  auto rightmost_col = 
    matrix | std::views::transform([](const auto& inner) -> const auto& {
               return inner.back();
             });
  // ...
}

Demo
或者您可以直接在matrix | std::views::join上进行二进制搜索(只有一行)

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

Demo

iklwldmw

iklwldmw2#

范围在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);
    }
};

https://godbolt.org/z/GhGWaWebh

相关问题