@gk1982: porównaj sobie czas wykonania twojego kodu i mojego, aby zobaczyć dlaczego mówimy, że O(n²) nadaje się tylko do /dev/null.
Twój kod (minimalnie zmodyfikowany output):
#include <iostream>
using namespace std;
int main()
{
int a, b;
cin >> a;
int tab[a];
for (int i = 0; i < a; i++) {
cin >> tab[i];
}
for (int i = 0; i < a; i++) {
int number = tab[i];
int count = 1;
for (int j = i + 1; j < a; j++) {
if (number == tab[j] && tab[j] >= 0) {
count++;
tab[j] = -1;
}
}
if (tab[i] >= 0)
cout << number << ": " << number - count << endl;
}
}
Kod mój:
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
int number_count;
cin >> number_count;
unordered_map<int, int> counts;
for(int i = 0; i < number_count; i++) {
int val;
cin >> val;
counts[val]++;
}
for(auto const& p : counts) {
cout << p.first << ": " << p.first - p.second << '\n';
}
}
Czas wykonania dla 300 000 elementów 0-9:
% make benchmark
time ./kq < input
8: -29880
0: -30040
1: -30155
5: -30041
3: -29820
6: -30019
7: -29864
4: -30144
9: -30061
2: -29931
real 0m0.037s
user 0m0.037s
sys 0m0.000s
time ./gk1982 < input
6: -30019
3: -29820
7: -29864
4: -30144
9: -30061
2: -29931
5: -30041
1: -30155
0: -30040
8: -29880
real 0m29.482s
user 0m29.208s
sys 0m0.007s
czyli ok 750x wolniej, jak powiększysz zbiór danych to będzie jeszcze gorzej. A tutaj nie wspominamy nawet o złożoności pamięciowej.