时间戳

首页 > 解决方案 > 通过降低出现频率对元素进行排序

c++ - 通过降低出现频率对元素进行排序

问题描述

我正在尝试解决这个问题：

如果 2 个数字具有相同的频率，则以递减的频率打印数组的元素，然后打印先出现的那个。（https://www.geeksforgeeks.org/sort-elements-by-frequency/）

我正在尝试自己实施解决方案。我曾想过创建以下数据结构：

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

我将数字本身存储在 firstint中，并且我将数组中数字的索引和计数存储在上图中的对中。

我想编写一个自定义比较器来对这些对进行排序，如下所示：

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

我仍在学习编写自定义比较器。我无法绕过我的头，我怎样才能通过比较器对地图进行排序。另外，如果对对进行排序，那么地图中的键是否会被排序？

请告诉我！谢谢！

标签： c++stl

解决方案

您不需要为此使用地图，或者更好的是，不用这种方式。您可以使用一个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是数组中元素的数量。

推荐阅读