Witam
Nie mam pomysłu na rozwiązania pewnego zadania, język C++
Mam tablicę, powiedzmy z 20 liczbami, z czego niektóre się powtarzają.
Jak wypisać te liczby, ale tak aby nie było wypisywania 2-3 razy tych samych liczb (czyli jak pomijać powtórzenia)
Tablica nie jest posortowana i nie chcę jej sortować.
Proszę tylko o wskazówki, sam chcę napisać.
Najłatwiej i najlepiej użyć std::unordered_set (tak jak tutaj), ale zakładam że jest to jakieś zadanie ze szkoły/studiów, wtedy możesz użyć std::vector aby przechowywać wypisane już liczby, lub po prostu tablicę.
Jeżeli zdecydujesz się na std::vector albo tablicę wtedy w pętli patrzysz czy te zbiory zawierają liczbę i z tablicy, jeżeli tak to pomiń a jeżeli nie to wypisz ją i dodaj do zbioru.
Wersja light (studencka) - dla małych liczb dodatnich:
#include <iostream>
#include <vector>
using namespace std;
int main() {
std::vector<int> v;
int a;
while(cin >> a) {
if (v.size() <= a) {
v.resize(a+1);
}
if (!v[a]) {
cout << a << ", ";
}
v[a] = a;
}
return 0;
}
Zależy z jakiego przedziału są to liczby, jeżeli są to liczby z małego przedziału, na przykład od 0-100, to najszybciej będzie jak zarezerwujesz tablice stuelemntową i przejdziesz po wszystkich liczbach pętlą
int a[20] = { 16, 2, 77, 40, 12, ... };
int*t= new int[100];
for (int i=0; i < 20; i++)
t[a[i]]=1;
delete t;
Na końcu wybierasz tylko te elementy tablicy, które są równe jeden. Złożoność obliczeniowa to O(k) gdzie k to długość przedziału, a złożoność pamięciowa to też k.
Przy przedziale większym na przykład 0-10000 to najlepiej dane mimo wszystko przesortować. Jeżeli zrobisz to QuickSortem to złożoność obliczeniowa wnosi O(nlog(n)), potem tylko sprawdzasz czy kolejny element tablicy jest taki jak poprzedni, jeżeli rożny to OK jeśli taki sam to go pomijasz, złożoność tej pętli to O(n) co w sumie daje O(nlog(n)).