Я пытаюсь реализовать метод двух указателей в наборах на С++. Я хочу проверить, равна ли разница двух элементов набора константе «k».
void solve(int n,int k,set<int> s){
auto it_1 = s.begin();
auto it_2 = s.end();
while(it_1 < it_2){
if (*it_2 - *it_1 == k){
cout << "YES" << endl;
return;
}
else if (*it_2 - *it_1 > k){
it_1++;
}
else{
it_2--;
}
}
cout << "NO" << endl;
return;
}
Я получаю следующую ошибку: -
error: no match for 'operator<' (operand types are 'std::_Rb_tree_const_iterator' and 'std::_Rb_tree_const_iterator') while(it_1 < it_2)
Я знаю, что ошибка в том, что я сравниваю два указателя. Как я могу проверить, находится ли это_1 позади это_2?
==
и !=
, но не поддерживают <
.
void solve(int n,int k,set<int> s)
-- Это подозрительно похоже на один из тех вопросов с сайтов, посвященных онлайн-соревнованиям по программированию. Если вы получили этот вопрос отсюда, вы не будете изучать C++, посещая эти сайты.
«Как я могу проверить, находится ли it_1 за it_2» — вы схлопываетесь слева и справа одним движением одного итератора (1 или 2) за итерацию. Итак, простое использование while (it_1 != it_2)
должно работать. Предостережение: это не решит проблему разыменования конечного итератора, о которой я упоминал ранее.
@PaulMcKenzie Я написал код в solve()
для лучшего понимания проблемы. Это не проблема любого из соревнований по кодированию. Спасибо за ваш комментарий!
@WhozCraig Раньше я использовал массивы, поэтому вы видите n
в коде. Спасибо за ваш комментарий !
Проблемы с итераторами решаются быстро.
!=
вместо <
end
-итератора, а на один элемент раньше. Потому что end
-итератор указывает на последний допустимый элемент.Но, к сожалению, подход с двумя указателями не сработает, если вы хотите найти пару с заданной дельтой. Причина этого в том, что вы увеличите один указатель слишком сильно, и дельта никогда не будет достигнута. С суммированием значений это сработает.
Давайте возьмем ваш первоначальный подход в качестве примера, исправим мелкие ошибки и посмотрим на результат:
#include <iostream>
#include <set>
void solve(int k, std::set<int>& s) {
auto it_1 = s.begin();
auto it_2 = std::prev(s.end());
while (it_1 != it_2) {
std::cout << *it_1 << ' ' << *it_2 << '\n';
if (*it_2 - *it_1 == k) {
std::cout << "YES\n";
return;
}
else if (*it_2 - *it_1 > k) {
it_1++;
}
else {
it_2--;
}
}
std::cout << "NO\n";
return;
}
int main() {
std::set test{ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
solve(8, test);
}
Это приведет к:
1 89
2 89
3 89
5 89
8 89
13 89
21 89
34 89
55 89
NO
Вы видите проблему.
Кстати, нахождение суммы — это типичный вариант использования подхода с двумя указателями. Тогда это всегда будет работать. Набор отсортирован. И мы начинаем с минимального значения в начале и максимального значения в конце. Таким образом, построение первой суммы даст нам максимально возможную сумму. Затем мы перемещаем сначала указатель с меньшими числами или, в зависимости от суммы, уменьшаем верхний указатель.
Пример:
#include <iostream>
#include <set>
void solve(int k, std::set<int>& s) {
auto it_1 = s.begin();
auto it_2 = std::prev(s.end());
while (it_1 != it_2) {
std::cout << *it_1 << ' ' << *it_2 << '\n';
if (*it_2 + *it_1 == k) {
std::cout << "YES\n";
return;
}
else if (*it_2 + *it_1 < k) {
it_1++;
}
else {
it_2--;
}
}
std::cout << "NO\n";
return;
}
int main() {
std::set test{ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
solve(8, test);
}
Выход:
1 89
1 55
1 34
1 21
1 13
1 8
1 5
2 5
3 5
YES
Но как решить дельта-проблему?
Что всегда будет работать, так это грубая сила. Это будет выглядеть так:
#include <iostream>
#include <set>
void solve(int k, std::set<int>& s) {
auto it_1 = s.begin();
auto it_2 = std::next(s.begin());
while ((it_1 != s.end()) and (it_2 != s.end())) {
std::cout << *it_1 << ' ' << *it_2 << '\n';
if ((it_1 != it_2) and ((*it_2 - *it_1 == k) or (*it_1 - *it_2 == k))) {
std::cout << "YES\n";
return;
}
else if (*it_2 - *it_1 < k)
++it_2;
else
++it_1;
}
std::cout << "NO\n";
return;
}
int main() {
std::set test{ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
solve(8, test);
}
Со следующим выводом:
1 2
1 3
1 5
1 8
1 13
2 13
3 13
5 13
YES
Немного оптимизированный подход будет использовать std::unordered_map
. Но, может быть, это слишком много для этого.
Это не единственная проблема.
if (*it_2...
разыменует конечный итератор последовательности при первом запуске, который вызывает неопределенное поведение. Кроме того, я не понимаю, какое отношение имеетn
ко всему этому, поэтому непонятно, почему он вообще предоставляется в качестве параметра дляsolve
. он никогда не используется в функции.