Задание "Can you get the loop?" на Codewars
Не могу понять, почему мой код не принимает Codewars, хотя я проверял решение у себя на компьютере, в CLion, и всё работает правильно.
Вот само задание в Codewars.
Вот мой вариант решения (+ дописал сам класс Node, но это чисто для того, чтобы проверить работу функции getLoopSize в CLion - в Codewars в решении сам класс я не вставлял):
#include <vector>
// Для std::binary_search.
#include <algorithm>
// Для тестов ниже.
#include <iostream>
class Node
{
public:
Node* nextNode = nullptr;
Node* getNext() { return nextNode; }
void setNext(Node* node) { nextNode = node; }
};
int getLoopSize(Node* startNode)
{
// Определяем, с какого элемента начинается цикл.
std::vector<Node*> nodes_ptr { startNode };
do
{
startNode = startNode->getNext();
bool isAlreadyThere = std::binary_search(nodes_ptr.begin(), nodes_ptr.end(), startNode);
if (isAlreadyThere) { break; }
else { nodes_ptr.push_back(startNode); }
} while (true);
// Определяем индекс повторяющегося элемента.
int index;
for (int i = 0; i < nodes_ptr.size(); ++i)
{
if (nodes_ptr[i] == startNode) { index = i; break; }
}
// Выводим длину цикла.
return nodes_ptr.size() - index;
}
Вот один из тестов, всё выполняется так, как и было задумано:
int main()
{
Node n1, n2, n3, n4;
n1.setNext(&n2);
n2.setNext(&n3);
n3.setNext(&n4);
n4.setNext(&n2);
// Выводит 3, как и задумано (у системы узлов tail = 1, loop = 3).
std::cout << getLoopSize(&n1) << std::endl;
return 0;
}
Тот же самый тест, но на Codewars, выдаёт мне следующее сообщение:
Incorrect answer for 4 nodes: tail of 1 node, and a loop of 3 nodes
Expected: equal to 3
Actual: 12
Ответы (2 шт):
std::binary_search работает только с отсортированными данными (не говоря уже о том что сложность поиска у него логарифмическая). Посему использовать надо std::find (у него к слову сложность линейная):
auto it = std::find(nodes_ptr.begin(), nodes_ptr.end(), startNode);
bool isAlreadyThere = it!=nodes_ptr.end();
Вы не с той стороны подходите к решению задачи.
Эта задача решается с помощью двух указателей; один на каждом шаге переходит на один узел вперед, второй — на два. Далее, рано или поздно, но за O(N) :), они совпадут — в этот момент вы находитесь уже в цикле, после чего найти его длину — задача тривиальная.
Ваш метод дает O(N^2), так как на каждом шаге требует просмотра всех пройденных узлов.