Liczenie ile razy każda z liczb w tablicy występuje.

0

Np. Wpisujemy 5
Później 5 liczb ( 2 2 3 3 3)
Program ma policzyć ile razy występuje liczba (np.2,2 razy i 3,3 razy), następnie odjąć ilość występowania liczby od jej wartości (np. 3-3=0, 2-2=0)

#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 b=0; b<a; b++)
    {

    }
    cout << endl;

}
6

Użyj std::unordered_map liczba ⟶ liczba wystąpień do policzenia. Jeśli mają być posortowane po liczbie, to użyj std::map

2

Bierzesz:
1) std::map<int, int> albo unordered_map, gdzie klucz określa liczbę, a wartość ilość wystąpień
2) iteratorem od map.begin() do map.end() jedziesz it->second - it->first

0
#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-count << endl; 

    }

}
0

Dodaje rozwiązanie z liczbami ujemnymi :)

#include <iostream>
#include <limits>
#include <math.h>
using namespace std;

int main()
{
    int a,b;
    cin>>a;

    double 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]&&!isnan(tab[j])){
               count++;

               tab[j]=std::numeric_limits<double>::quiet_NaN();
         }

        }

        if(!isnan(tab[i])) 
        cout << number-count << endl; 

    }

}
3

Ten kod nie dość, że jest bardziej skomplikowany, niż użycie (unorderred_)map to na dodatek ma złożoność kwadratową.
na dodatek piewrsze użycie isnan jest zbędne, bo NaN jest nierówne każdej wartości (nawet sama sobie).
Jeszcze wynik jest wyświetlany bezsensu (pewnie typo/copy-paste).

Swoją drogą mierzi mnie kod C z klasami.

1
#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main()
{
    vector<int> numbers = { 1, 3, 4, 3, 1, 1, 5, 6 };
    map<int, int> grouped;

    for (auto &n : numbers)
    {
        ++grouped[n];
    }

    for (auto &g : grouped)
    {
        cout << "Number: " << g.first << " Count: " << g.second << "\n";
    }

    return 0;
}

Pewnie da się to zrobić bardziej w stylu C++ więc wybaczcie jeśli ten kod jest trochę passe. Dawno nie pisałem w tym języku.

2

@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.

0

Poprawiony kod działający na int z liczbami ujemnymi, bez tego mojego wygłupu z double i nan. I to jeszcze nie mój ostatni programik na tablicach, jeszcze coś poprawię żeby był szybszy i nie kwadratowy.

using namespace std;

int main()
{
    int a;
    cin>>a;

    int tab[a];
    bool tabb[a];

    for(int i=0; i<a; i++)
    {
        cin >> tab[i]; 
        tabb[i]=true;
    }

    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]&&tabb[j]==true){
               count++;

               tabb[j]=false;
         }

        }

        if(tabb[i]==true) 
        cout << "Number - count: ("<<tab[i]<<") "<<" - ("<<count<<") = "<<number-count << endl; 

    }

}
2

Tak długo jak masz dwa zagnieżdżone for-y to nie osiągniesz złożoności niekwadratowej Bracie.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0