Witam
Jak można zaimplementować taką funkcję, która by sprawdzała czy podana liczba już nie wystąpiła? Mi nic innego do głowy nie przychodzi poza tym co niżej, czyli rozwiązaniem pamięciożernym, które z czasem może być no i z czasem to szukanie może być czasochłonne jeżeli byśmy użyli seta zamiast unordered_seta. Kolega miał takie pytanie na rozmowie kwalifikacyjnej o pracę. Podejrzewam, że jest jaki myk/sztuczka ale pojęcia nie mam jaka. Chociaż nie mogę sobie nawet wyobrazić jaka to może być ta sztuczka, przecież musisz zapamiętać wszystkie liczby, więc musi to być rozwiązanie pamięciożerne. Co to długiego szukania, wstawiania to tutaj mamy złożoność czasową wydaje mi się O(1) (jeżeli tylko max load factor jest ustawiony na 1 i rehash nie występuje). Jakby był set to by było O(log(n)). Tak średnio jestem tego pewny, musze jeszcze o tym poczytać.
#include <stdio.h>
#include <iostream>
#include <unordered_set>
using namespace std;
bool sprawdz(const unsigned& x)
{
static unordered_set<unsigned> checkTable;
if(checkTable.find(x) != checkTable.end())
return true;
checkTable.insert(x);
}
int main()
{
cout << sprawdz(6) << endl;
cout << sprawdz(45) << endl;
cout << sprawdz(1) << endl;
cout << sprawdz(6) << endl;
return 0;
}