Question

Căutare într-un șir aproape sortat - Problema C++

Bogdan a învățat programare de pe WellCode și a aplicat pentru un job la o companie mare de IT. La interviul tehnic, a primit următoarea problemă:

Se dă un şir de n numere naturale care are o proprietate mai specială. Iniţial, el a fost sortat crescător, dar i s-au aplicat un număr necunoscut de permutari circulare spre stânga. Se mai dau k valori întregi. Află care dintre cele k valori apar în primul șir.

Bogdan s-a descurcat la interviu şi a fost angajat! Acum este rândul tău să rezolvi problema.

Date de intrare
Programul citeşte de pe prima linie un număr natural n, iar de pe urmatoarea linie un şir format din n numere naturale, având proprietățile din enunț. Pe cea de-a 3-a linie se citeşte un număr natural k, iar pe urmatoarea linie k valori întregi, reprezentând numerele pe care trebuie să le cauți în șir.

Date de ieşire
Programul afişează pe ecran, pentru fiecare din cele k valori, daca se găsește sau nu în şirul dat. Daca x se găseşte în şir se va afişa mesajul "x se gaseste in sir". In caz contrar, se va afisa mesajul "x nu se gaseste in sir". (Unde în loc de x vei afișa numărul întreg căutat)

Aceasta este o PROBLEMĂ DE INTERVIU cu care e posibil să te întâlnești atunci când aplici pentru joburi de programator!

Restricţii şi precizări
0 < n ≤ 50 000
numerele din ambele șiruri au valori în intervalul (0, 1 000 000 000]
0 < k ≤ 10 000
Exemplu
Date de intrare
7
5 12 15 17 20 2 4
4
1 15 5 7

Date de ieșire
1 nu se gaseste in sir
15 se gaseste in sir
5 se gaseste in sir
7 nu se gaseste in sir

Answer 1

Răspuns:

Cum n e asa de mic cred ca se poate si asa, in O(N + K)

Explicație:

#include <bits/stdc++.h>

using namespace std;

const int N = 5e4;

int n, a[N], k, num;

unordered_map<int, bool> m;

int main(){

   cin >> n;

   for(int i = 0; i < n; i++){

       cin >> a[i];

       m[a[i]] = 1;

   }

   cin >> k;

   while(k--){

       cin >> num;

       cout << num << " nu se gaseste in sir\n" + m[num] * 3;

   }

}