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

Odpowiedz Nowy wątek
2019-01-10 18:22
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;

}

Pozostało 580 znaków

2019-01-10 18:37
kq
6

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


Pozostało 580 znaków

2019-01-10 18:51
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


"Sugeruję wyobrazić sobie Słońce widziane z orbity Merkurego, a następnie dupę tej wielkości. W takiej właśnie dupie specjalista ma teksty o wspaniałej atmosferze, pracy pełnej wyzwań i tworzeniu innowacyjnych rozwiązań. Pracuje się po to, żeby zarabiać, a z resztą specjalista sobie poradzi we własnym zakresie, nawet jeśli firma mieści się w okopie na granicy obu Korei."
-somekind,
konkretny człowiek-konkretny przekaz :]
edytowany 1x, ostatnio: MasterBLB, 2019-01-10 18:51
2) ranged for panie kolego ;​) - kq 2019-01-10 18:52
Jeśli da się w C++11 wyciągnąć w nim iterator, to jak najbardziej. - MasterBLB 2019-01-11 10:25
A po co tam iterator? value_type to para klucz⟶wartość - kq 2019-01-11 14:15

Pozostało 580 znaków

2019-01-10 19:20
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; 
 
    }
 
}

Każdy programista przybywający z innego miasta jest fachowcem.
edytowany 4x, ostatnio: gk1982, 2019-01-10 20:49
Pokaż pozostałe 13 komentarzy
Powiem, że ma złe rozwiązanie. - kq 2019-01-11 15:35
A jak taki programista ma wiedzieć później jak zrobić arraylist czy linkę list czy mapę. Jak nie opanuje tablic. - gk1982 2019-01-11 17:03
99% takich programistów nie ma potrzeby reimplementacji biblioteki standardowej. - kq 2019-01-11 17:04
Lepiej by wiedział jak każda ze struktur działa i kiedy której użyć. - Delor 2019-01-11 17:06
@Delor: ale przede wszystkim lepiej, jeśli nauczy się jakie pojemniki do czego się nadają. Tutaj przykładowo, tablica się nie nadaje. - enedil 2019-01-11 17:42

Pozostało 580 znaków

2019-01-10 21:45
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; 
 
    }
 
}

Każdy programista przybywający z innego miasta jest fachowcem.
edytowany 1x, ostatnio: gk1982, 2019-01-10 21:46
czekaj czekaj, a po co Tobie te double? - enedil 2019-01-10 23:39
a da się int ustawić jako NaN ? - gk1982 2019-01-10 23:51
Oczywiście że nie, ale dlaczego chciałbyś to robić? - enedil 2019-01-11 01:45
Ustawiam znacznik żeby w pętli nie brało pod uwagę danego elementu tab. - gk1982 2019-01-11 07:16

Pozostało 580 znaków

2019-01-11 10:55
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.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 4x, ostatnio: MarekR22, 2019-01-11 14:29

Pozostało 580 znaków

2019-01-11 11:32
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.

edytowany 1x, ostatnio: grzesiek51114, 2019-01-11 11:37
Jest spoko, ale unordered map ma lepszą typową złożoność ;​) - kq 2019-01-11 14:14
To i tak jest poprawiony kod. Zamiast ++grouped[n] było wywołanie funkcji plus warunek sprawdzający klucze. @MarekR22 podpowiedział mi, że mogę skorzystać z operatora. Szczerze mówiąc nawet nie pamiętałem, że można tak wstawiać do mapy. ;) - grzesiek51114 2019-01-11 14:16
Ja bym w sumie zrobił tu postinkrementację, ale nie ma to żadnego znaczenia w tym przypadku, poza osobistą preferencją ;​) - kq 2019-01-11 14:18
@grzesiek51114: Pewnie nawyk z tablic, żeby przed odwołaniem się do elementu najpierw sprawdzić indeks. Często sam się na tym łapie - tajny_agent 2019-01-11 15:43

Pozostało 580 znaków

2019-01-11 16:12
kq
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.


Pokaż pozostałe 6 komentarzy
@gk1982: nie zgadzasz się z aksjomatami? :) - grzesiek51114 2019-01-11 18:03
Przyjadę do domu to poprawię te moje głupie programy bo wczoraj jeszcze nie umiałem jak dzisiaj Ale tez na tablicach. - gk1982 2019-01-11 18:05
Nie zgadzam się nawet z tym że istnieje czas ruch i energia. - gk1982 2019-01-11 18:07
Przychodzi uczeń do piekarni i pyta się jak zrobić bułkę. Weź zamrożone ciasto i włóż do pieca :p - gk1982 2019-01-11 18:12
Nie, pójdź do rolnika, kup zboże i zrób z tego mąkę za pomocą kuli do ucierania ciasta. - kq 2019-01-11 18:14

Pozostało 580 znaków

2019-01-11 18:39
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; 
 
    }
 
}

Każdy programista przybywający z innego miasta jest fachowcem.

Pozostało 580 znaków

2019-01-11 18:49
2

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


"Sugeruję wyobrazić sobie Słońce widziane z orbity Merkurego, a następnie dupę tej wielkości. W takiej właśnie dupie specjalista ma teksty o wspaniałej atmosferze, pracy pełnej wyzwań i tworzeniu innowacyjnych rozwiązań. Pracuje się po to, żeby zarabiać, a z resztą specjalista sobie poradzi we własnym zakresie, nawet jeśli firma mieści się w okopie na granicy obu Korei."
-somekind,
konkretny człowiek-konkretny przekaz :]
Ok dzięki postaram się zrobić, chyba to możliwe. - gk1982 2019-01-11 18:57

Pozostało 580 znaków

2019-01-11 19:09
3

Tutaj moja implementacja, używa tylko tablic, i na dodatek jest szybsza od implementacji @kq :D
Dodatkowo sortuje liczby na wyjściu (1)

#include <array>
#include <algorithm>
#include <iostream>
#include <vector>
 
#include <experimental/array>
 
using std::cin;
using std::cout;
using std::array;
using std::vector;
 
const int p = 32719;
 
void inc(array<vector<array<int,2>>, p>& arr, int index)
{
    auto ind = index % p;
    auto r = index/p;
    auto it = std::find_if(std::begin(arr[ind]), std::end(arr[ind]),
            [r](auto el) {return el[0] == r;});
    if (it == std::end(arr[ind])) {
        arr[ind].emplace_back(std::experimental::make_array(r, 1));
    } else {
        (*it)[1]++;
    }
}
 
int main()
{
    array<vector<array<int,2>>, p> arr;
    int a;
    cin >> a;
    while (a--) {
        int n;
        cin >> n;
        inc(arr, n);
    }
    for (int i = 0; i < p; ++i) {
        for (size_t j = 0; j < arr[i].size(); ++j) {
            cout << arr[i][j][0]*p+i << ": "
                 << arr[i][j][0]*p+i - arr[i][j][1] << "\n";
        }
    }
}

Oto wynik benchmarka na moim komputerze:

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.043s
user    0m0.041s
sys 0m0.001s
time ./gk1982 < input
6: -30019
3: -29820
7: -29864
4: -30144
9: -30061
2: -29931
5: -30041
1: -30155
0: -30040
8: -29880

real    0m30.246s
user    0m30.115s
sys 0m0.008s
time ./enedil < input
0: -30040
1: -30155
2: -29931
3: -29820
4: -30144
5: -30041
6: -30019
7: -29864
8: -29880
9: -30061

real    0m0.040s
user    0m0.039s
sys 0m0.001s

(1) uwaga: nie jest to zwyczajny porządek na liczbach całkowitych

edytowany 2x, ostatnio: enedil, 2019-01-11 19:12
Przy jednym teście to granica błędu statystycznego ;​) Ale propsuję bardzo - kq 2019-01-11 19:16
@kq: przy takim teście to najszybsza by była tablica zliczająca ilość wystąpień :D (ale moje rozwiązanie działa dla wszystkich liczb. - enedil 2019-01-11 19:24
Założenie jest że wartości są dla całego zakresu wartości int-a, do 10 dałem, bo inaczej output by był za długi do posta. - kq 2019-01-11 19:25
Domyśliłem się - enedil 2019-01-11 19:26

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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