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.

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

0

Uwaga doszedłem do poziomu tablicy zliczającej ilość wystąpień, ale jutro jeszcze postaram się żeby działało tez na liczby ujemne :)

#include <iostream>
using namespace std;
 
int main()
{
    int a;
    cin>>a;
 
 	int max = 0;
 	int min = 0;
 	
    int tab[a];  
 
 	cin >> tab[0];
 	max = tab[0];
 	min = tab[0];

    for(int i=1; i<a; i++)
    {
        cin >> tab[i]; 
		if(tab[i]>max) max=tab[i];
		if(tab[i]<min) min =tab[i];
    }
    
    int tabc[max];

    
    for(int i=min;i<=max;i++)
    {
    	tabc[i]=0;
	}
    
 
    for(int i=0;i<a;i++)
    {
    	tabc[tab[i]]=tabc[tab[i]]+1;	
    }
    
    for(int i=min;i<=max;i++) {
    
	if(tabc[i]>0) 	cout << "Number - count: ("<<i<<") "<<" - ("<<tabc[i]<<") = "<<i-tabc[i] << endl;
	}

    
}

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