#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>

using namespace std;

/**
   Program ten pokazuje, jak wydajniejszy algorytm może znacznie przyspieszyć
   zadanie znajdowania w wektorze najczęściej występującego elementu.
*/

/**
   Zlicza, ile razy w wektorze występuje dana wartość.
   @param a wektor
   @param value wartość do zliczania
   @return liczba wystąpień danej wartości w wektorze a
*/
int count(vector<int> a, int value)
{
   int count = 0;
   for (int i = 0; i < a.size(); i++)
   {
      if (a[i] == value) { count++; }
   }
   return count;
}

/**
   Oblicza największą wartość w wektorze.
   @param a wektor
   @return największa wartość w wektorze a
*/
int max(vector<int> values)
{
   int largest = values[0];
   for (int i = 1; i < values.size(); i++)
   {
      if (values[i] > largest)
      {
         largest = values[i];
      }
   }
   return largest;
}

/**
   Znajduje w wektorze wartość przy użyciu algorytmu
   wyszukiwania liniowego.
   @param a wektor do przeszukania
   @param value szukana wartość
   @return indeks, pod którym występuje ta wartość lub -1,
   jeśli nie występuje ona w wektorze
*/
int search(vector<int> a, int value)
{
   for (int i = 0; i < a.size(); i++)
   {
      if (a[i] == value) { return i; }
   }
   return -1;
}

/**
   Zwraca najczęściej występującą w wektorze wartość.
   @param a wektor
   @return wartość najczęściej występująca w wektorze a
*/
int most_frequent1(vector<int> a)
{
   vector<int> counts(a.size());
   for (int i = 0; i < a.size(); i++) // O(n*n)
   {
      counts[i] = count(a, a[i]); // O(n) w każdej iteracji
   }

   int highest_frequency = max(counts); // O(n)
   int highest_frequency_index = search(counts, highest_frequency); // O(n)
   return a[highest_frequency_index];
}

/**
   Zwraca najczęściej występującą w wektorze wartość.
   @param a wektor
   @return wartość najczęściej występująca w wektorze a
*/
int most_frequent2(vector<int> a)
{
   sort(a.begin(), a.end()); // O(n log(n))
   vector<int> counts(a.size());

   int count = 0;
   for (int i = 0; i < a.size(); i++) // O(n)
   {
      count++;
      if (i == a.size() - 1 || a[i] != a[i + 1])
      {
         counts[i] = count;
         count = 0;
      }
   }

   int highest_frequency = max(counts); // O(n)
   int highest_frequency_index = search(counts, highest_frequency); // O(n)
   return a[highest_frequency_index];
}

int main()
{
   srand(time(0));
   vector<int> values;
   cout << "Poszczególnych liczb ma być: ";
   int k;
   cin >> k;

   // Dodaje raz 1, dwa razy 2, trzy razy 3, ... , k razy k
   for (int i = 1; i <= k; i++)
   {
      for (int j = 1; j <= i; j++)
      {
         values.push_back(i);
      }
   }
   // Funkcja ta układa liczby w wektorze w kolejności losowej.
   random_shuffle(values.begin(), values.end());

   // Kopiuje wartości do wektora i uruchamia pierwszą wersję
   // algorytmu.
   vector<int> a = values;
   int before = time(0);
   int result = most_frequent1(a);
   int after = time(0);
   cout << result << endl;
   cout << "Spodziewana liczba: " << k << endl;
   cout << "Czas wykonania: " << after - before << " sekund(y)" << endl;

   // Kopiuje te same wartości i uruchamia drugą wersję.
   vector<int> b = values;
   before = time(0);
   result = most_frequent2(b);
   after = time(0);
   cout << result << endl;
   cout << "Spodziewana liczba: " << k << endl;
   cout << "Czas wykonania: " << after - before << " sekund(y)" << endl;

   return 0;
}

