如何按每个数字的频率降序排列数组?

我想我会这样做:

现在遍历所有数字。如果数字还不知道(在数据结构中),添加它,记住当前索引以及1作为计数。否则,增加计数。

现在,按照出现次数(减少)和出现次数索引(增加)对数据结构内容进行排序,并输出结果(使用出现次数重复数字)。

使用的处理空间<=N、 使用的时间取决于数据结构和字典可能大约为O(N logn)

我可以想出两个解决办法:

进行第一次遍历以计算频率并存储第一个索引,然后根据该索引进行排序

这很容易实现,在最坏的情况下使用线性(O(N))额外内存,并且需要O(N logn)时间。

每件事都要一次完成 priority queue ,其中“priority”是频率计数(当您通过输入时会发生变化)和第一次中断连接的索引

或 蟒蛇3.1

>>> from collections import Counter
>>> L=[5, 13, 6, 5, 13, 7, 8, 6, 5]
>>> c=Counter(L)
>>> def keyfunc(x):
...     return (-c.get(x),L.index(x))
... 
>>> sorted(L,key=keyfunc)
[5, 5, 5, 13, 13, 6, 6, 7, 8]

在 蟒蛇2.6

>>> from collections import defaultdict
>>> L=[5, 13, 6, 5, 13, 7, 8, 6, 5]
>>> c=defaultdict(int)
>>> for x in L:
...     c[x]+=1
... 
>>> def keyfunc(x):
...     return (-c.get(x),L.index(x))
... 
>>> sorted(L,key=keyfunc)
[5, 5, 5, 13, 13, 6, 6, 7, 8]

(奇怪的约束)

>>> L=[5, 13, 6, 5, 13, 7, 8, 6, 5]
>>> c={}
>>> for x in L:
...     c[x]=c.setdefault(x,0)+1
... 
>>> def keyfunc(x):
...     return (-c.get(x),L.index(x))
... 
>>> sorted(L,key=keyfunc)
[5, 5, 5, 13, 13, 6, 6, 7, 8]

在每种情况下,keyfunc都用于控制排序的顺序

keyfunc(5) returns (-3,0)
keyfunc(6) returns (-2,2)
keyfunc(7) returns (-1,5)
keyfunc(8) returns (-1,6)
keyfunc(13) returns (-2,1)

列表项根据keyfunc的返回值进行排序

但是-作为第一步,您应该使用一个std::map/对来存储数字,或者如果您事先被告知值的范围,那么使用一个简单的数组来执行2pass解决方案。

C#。它采用最明显的方法:按频率和顺序排序。

输出: 5 5 5 13 13 6 6 7 8 空格:O(n)。时间:O(n logn)。

class Program
{
    class FreqAndOrdinal
    {
        public int Frequency;
        public int Ordinal;
        public FreqAndOrdinal(int freq, int ord)
        {
            this.Frequency = freq;
            this.Ordinal = ord;
        }
    }

    static int Compare(FreqAndOrdinal x, FreqAndOrdinal y)
    {
        int result = y.Frequency.CompareTo(x.Frequency);
        return result == 0 ? x.Ordinal.CompareTo(y.Ordinal) : result;
    }

    static void Main(string[] args)
    {
        int[] nums = new int[] { 5, 13, 6, 5, 13, 7, 8, 6, 5 };
        var freqLookup = new Dictionary<int, FreqAndOrdinal>(nums.Length);
        for (int i = 0; i < nums.Length; i++)
        {
            FreqAndOrdinal tmp;
            if (freqLookup.TryGetValue(nums[i], out tmp))
                ++tmp.Frequency;
            else
                freqLookup[nums[i]] = new FreqAndOrdinal(1, i);
        }

        Array.Sort(nums, (x,y) => Compare(freqLookup[x], freqLookup[y]));

        for (int i = 0; i < nums.Length; i++)
        {
            Console.Write(" {0}", nums[i]);
        }
        Console.ReadKey();
    }
}

对数组排序,并在排序函数中为x,y:按计数(x)和计数(y)排序。如果它们相同,则按索引(x)和索引(y)排序

在python中:

input = [5, 13, 6, 5, 13, 7, 8, 6, 5]
orig = list(input)

def cmp(x, y):
    if (orig.count(y) - orig.count(x) != 0):
        return orig.count(y) - orig.count(x)
    return orig.index(x) - orig.index(y)   

input.sort(cmp) 
print input

为了提高效率,请在排序数组之前预先计算计数和索引。

private static void sortByFrequency(int[] a)
{
    Map<Integer, Element> map = new HashMap<Integer, Element>();
    for(int i=0; i<a.length; i++)
    {
        if(map.get(a[i]) == null)
        {
            map.put(a[i], new Element(i));
        }
        else
        {
            Element e = map.get(a[i]);
            e.frequency++;
        }
    }

    Set<Integer> set = map.keySet();
    TreeSet<Element> treeSet = new TreeSet<Element>();
    for(int i : set)
    {
        treeSet.add(map.get(i));
    }

    for(Element e : treeSet)
    {
        for(int i=0; i<e.frequency;i++)
        {
            System.out.println(a[e.index]);
        }
    }
}

private static class Element implements Comparable<Element>
{
    private final int index;
    private int frequency;

    Element(int index)
    {
        this.index = index;
        this.frequency = 1;
    }

    @Override
    public int compareTo(Element o)
    {
        int k = o.frequency - this.frequency;
        if(k != 0) return k;
        else
        {
            return this.index - o.index;
        }
    }
}

public static void main(String[] args)
{
    int[] a = {5, 13, 6, 5, 13, 7, 8, 6, 5};
    sortByFrequency(a);
}