输入: {5, 13, 6, 5, 13, 7, 8, 6, 5}
输出: {5, 5, 5, 13, 13, 6, 6, 7, 8}
问题是按照频率的降序排列数组中的数字,保留它们出现的顺序.
如果存在平局,例如在13和6之间的示例中,那么输入数组中首先出现的数字将首先出现在输出数组中.
我想我会这样做:
使用键值数据结构,其中数字本身是键,出现次数和第一次出现索引是值.
现在遍历所有数字.如果数字尚未知晓(在数据结构中),请添加它,记住当前索引以及1作为计数.否则,递增计数.
现在按出现次数(减少)和出现次数(增加)对数据结构内容进行排序,并输出结果(使用出现次数重复该次数).
使用的处理空间<= N,根据数据结构和字典使用的时间可能约为O(N log N)