Найти частоту каждого элемента массива

Question

У меня есть этот хакерранк.N должно быть <= 1 000 000. Каждый элемент должен быть между 20 и 50, но я не знаю, как это сделать, не выполняя много соревновательного программирования.Пользователь вводит N номеров.Программа находит частоты каждого элемента и печатает их по убыванию.Я попытался сделать цикл while (см. В основном), но это не сработало.Пожалуйста, помогите. </p>

Формат ввода:

9

42 42 34 26 42 35 34 47 47

Вывод:

42 3

34 2

47 2

26 1

35 1

#include <iostream>
#include <algorithm>
using namespace std;

struct ele
{
    int count, index, val;
};


bool mycomp(struct ele a, struct ele b) {
    return (a.val < b.val);
}

bool mycomp2(struct ele a, struct ele b) {
     if (a.count != b.count) return (a.count < b.count);
    else return a.index > b.index;
}

void sortByFrequency(int arr[], int n)
{
    struct ele element[n];
    for (int i = 0; i < n; i++)
    {
        element[i].index = i;
        element[i].count = 0;
        element[i].val = arr[i];

    }

    stable_sort(element, element + n, mycomp);

    element[0].count = 1;

    for (int i = 1; i < n; i++)
    {
        if (element[i].val == element[i - 1].val)
        {
            element[i].count += element[i - 1].count + 1;

            element[i - 1].count = -1;

            element[i].index = element[i - 1].index;
        }

        else element[i].count = 1;
   }
   stable_sort(element, element + n, mycomp2);
   for (int i = n - 1, index = 0; i >= 0; i--)
       if (element[i].count != -1)
           for (int j = 0; j < element[i].count; j++)
               arr[index++] = element[i].val;
   }

int main() {
    int n; cin >> n;
    int* arr = new int[n];
    int* seen = new int[n];

    for (int i = 0; i < n; i++){
        while(arr[i] < 20 || arr[i] > 50) 
        cin >> arr[i];
    }

    sortByFrequency(arr, n);

        for (int i = 0; i < n; i++) {
        if (seen[i] == 0) {
            int count = 0;
           for (int j = i; j < n; j++)
                if (arr[j] == arr[i]) {
                    count += 1;
                    seen[j] = 1;
                }
            cout << arr[i] << " " << count << endl;
        }
    }
}

Answer 1

Не то, чтобы я считал соревновательное программирование полезным для улучшения навыков программирования. (По крайней мере, не навыки программирования для повседневного бизнеса.) Однако я испытал искушение и не смог устоять. (Это утро понедельника и, может быть, хорошая разминка на неделю.)

Составив идеи комментариев я получил это:

#include <cassert>
#include <iostream>
#include <vector>
#include <set>

int main()
{
  // input and count frequency
  int n; std::cin >> n;
  assert(n >= 0 && n < 1000000);
  const int valueMin = 20, valueMax = 50;
  int freq[valueMax - valueMin + 1] {};
  for (int i = 0; i < n; ++i) {
    int value; std::cin >> value;
    ++freq[value - valueMin];
  }
  // sort frequency
  std::set<std::pair<int, int>, bool(*)(const std::pair<int, int>&, const std::pair<int, int>&)>
    freqSorted([](const std::pair<int, int> &pair1, const std::pair<int, int> &pair2) {
      if (pair1.first != pair2.first) return pair1.first > pair2.first;
      return pair1.second < pair2.second;
    });
  for (int i = valueMin; i <= valueMax; ++i) {
    if (const int freqI = freq[i - valueMin]) {
      freqSorted.insert(std::make_pair(freqI, i));
    }
  }
  // output
  for (std::pair<int, int> entry : freqSorted) {
    std::cout << entry.second << ' ' << entry.first << '\n';
  }
}

Примечания:

1. Я использую

   const int valueMin = 20, valueMax = 50;
   int freq[valueMax - valueMin + 1] {};
   

   для хранения количества вхождений с минимальным объемом памяти. (Явное ограничение диапазона для входных значений меня обнадежило.)

2. user4581301 сделал меня чувствительным в отношении потребления памяти. (До прочтения я не осознавал, что хранение входных значений на самом деле не нужно.)

3. Использование std::map (как рекомендовано Вишну Дасу) было моей первой идеей. При тестировании я задавался вопросом о пропущенных результатах, пока не понял, что map с номером вхождения в качестве ключа будет хранить только одно из нескольких значений с одинаковой частотой. Поэтому я изменил его на std::set с обоими значениями в качестве ключа.

Выход:

42 3
34 2
47 2
26 1
35 1

Демонстрация в реальном времени на coliru