Сортировка элементов по убыванию частоты появления

Question

Я пытаюсь решить вопрос:

Вывести элементы массива с уменьшающейся частотой, если 2 числа имеют одинаковую частоту, а затем вывести первое.(https://www.geeksforgeeks.org/sort-elements-by-frequency/)

Я пытаюсь реализовать решение самостоятельно. Я думал о создании следующей структуры данных:

map<int,pair<int,int>> mymap

Я сохраняюсамо число в первом int, и я храню индекс и счетчик числа в массиве в паре на карте выше.

Я хочу написать собственный компаратор для сортировки пар, что-токак это:

bool cmp(pair<int,int>&a, pair<int,int>&b)
{
    if (a.first == b.first) 
         return a < b;
    else
         return a > b;
}

Я все еще учусь писать собственные компараторы. Я не могу обернуть вокруг себя голову, вот как я могу передать компаратор для сортировки карты. Также, если пары отсортированы,тогда ключ на карте будет отсортирован рядом?

Пожалуйста, дайте мне знать! Спасибо!

Answer 1

Вам не нужно использовать карты для этого или, лучше, не таким образом.Вы можете использовать базовый массив arr, который будет содержать элементы, а затем использовать map cnt<int,int>, который будет хранить количество экземпляров каждого элемента в массиве, и еще один firstIndex<int,int>, который будет сохранять индекс первого появления элемента.элемент.В этом случае функция сортировки становится просто:

bool cmp(int a, int b)
{
    if(cnt[a] != cnt[b]){
      return cnt[a] > cnt[b];
    } else {
      return firstIndex[a] < firstIndex[b];
    }
}

используйте ее так:

sort(arr, arr+n, cmp);

, где n - количество элементов в массиве.