如何安排的递减顺序每个数字频率的阵列？ [英] How to arrange an array in decreasing order of frequency of each number?

问题描述

输入： {5，13，6，5，13，7，8，6，5}

输出： {5,5，5，13，13，6，6，7，8}

问题是安排在阵列中的数字递减顺序的频率，$ P $的pserving它们发生的次序。

The question is to arrange the numbers in the array in decreasing order of their frequency, preserving the order of their occurrence.

如果有13和6之间的配合，像在本实施例，则输入阵列中发生的第一数目将先到的输出阵列中的

If there is a tie, like in this example between 13 and 6, then the number occurring first in the input array would come first in the output array.

推荐答案

我想我会做这样的：

使用一个键 - 值数据结构，其中的数目本身是关键和出现计数与第一发生指数是值

Use a key-value data structure where the number itself is the key and the occurrence count and first occurrence index are the value.

现在遍历所有的数字。如果数字尚不清楚（在数据结构），添加它，记住当前索引以及1作为计数。否则，增加计数。

Now traverse all numbers. If the number is not yet known (in the data structure), add it, remembering the current index as well as 1 as count. Otherwise, increment the count.

现在由出现计数（递减）和发生指数（增加），并输出结果（使用出现计数的重复数）。

Now sort the data structure contents by the occurrence count (decreasing) and the occurrence index (increasing), and output the result (repeating the number using the occurrence count).

使用的，其中加工空间; = N，时间根据使用的数据结构和字典很可能是约O（N日志N）

Processing space used <= N, time used depending on data structure and dictionary would probably be about O(N log N)

这篇关于如何安排的递减顺序每个数字频率的阵列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！