Как расположить массив в порядке убывания частоты каждого числа?

Question

Ввод: {5, 13, 6, 5, 13, 7, 8, 6, 5}

Выход: {5, 5, 5, 13, 13, 6, 6, 7, 8}

Вопрос состоит в том, чтобы расположить числа в массиве в порядке убывания их частоты, сохраняя порядок их появления.

Если есть связь, как в этом примере между 13 и 6, то число, встречающееся первым во входном массиве, будет первым в выходном массиве.

Answer 1

Думаю, я бы сделал это так:

Используйте структуру данных ключ-значение, в которой само число является ключом, а счетчик вхождений и индекс первого вхождения являются значением.

Теперь пройдитесь по всем числам. Если число еще не известно (в структуре данных), добавьте его, запомнив текущий индекс, а также 1 в качестве счетчика. В противном случае увеличьте счет.

Теперь отсортируйте содержимое структуры данных по количеству вхождений (уменьшается) и индексу вхождения (увеличивается), и выведите результат (повторяя число с использованием счетчика вхождений).

Используемое пространство обработки <= N, время, используемое в зависимости от структуры данных и словаря, вероятно, будет около O (N log N) </p>

Answer 2

Я могу придумать два решения:

Сделайте первый проход для подсчета частот и сохраните первый индекс, а затем отсортируйте в соответствии с этим

Это просто реализовать, использует линейную (O (N)) дополнительную память в худшем случае и занимает O (N log N) времени.

Делайте все за один проход с какой-то очередью приоритетов , где "приоритет" - это счетчик частоты (меняется при прохождении через вход) и индекс первого вхождения для разрыва связей

Это делает все за один проход, но я не могу думать о каком-либо преимуществе над другим решением. Это все еще требует O (N) дополнительной памяти, и также займет O (N log N) время. Также требуется более сложная структура данных.

Answer 3

In Python2.7 или Python3.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]

In Python2.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

Answer 4

C #. Это самый очевидный подход: сортировка по частоте и порядковому номеру.

Выход: 5 5 5 13 13 6 6 7 8. Пробел: O (n). Время: O (n log n).

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();
    }
}

Answer 5

Скорее всего, вы можете сделать это за один проход с помощью алгоритма типа пузырьковой сортировки, где вы сохраняете заметку о количестве предыдущего значения и меняете группы чисел, когда вы найдете больше другого числа.

Но - в качестве первого шага вы должны выполнить двухпроходное решение, используя std :: map / pair для хранения номера или если вам заранее сообщают о диапазоне значений, используйте простой массив.

Answer 6

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);
}

Answer 7

Сортировка массива, и в вашей функции сортировки по x, y: сортировка по числу (x) против количества (y). Если они одинаковые, сортируйте по индексу (x) и индексу (y)

В питоне:

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

Чтобы сделать его более эффективным, предварительно просчитайте число и индексы перед сортировкой массива.