Частотная сортировка

Question

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

Пример ввода: 3,4,3,2,3,5,4,2,2,1,2
Пример вывода: 1 5 4 3 2

Answer 1

Если разрешено дополнительное пространство: перейдите к входу и выполните частотный анализ. Запишите это в какую-нибудь хеш-таблицу. Это значит примерно:

for each x in input:
  if x in table:
    ++table[x]
  else
    table.insert(x)

Затем простая быстрая сортировка по уникальным значениям с функцией сравнения, учитывающей частоту, а не само значение.

То есть:

function freq_compare (x, y):
  return compare(table[x], table[y])

Где compare - числовое значение для частот.

Answer 2

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

Answer 3

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

import java.io.*;
import java.util.*;
import java.lang.*;
public class Sum_of
{
 public static HashMap<Integer, Integer> sortHashMapByValues(
    HashMap<Integer, Integer> passedMap) {
List<Integer> mapKeys = new ArrayList<>(passedMap.keySet());
List<Integer> mapValues = new ArrayList<>(passedMap.values());
Collections.sort(mapValues);
Collections.sort(mapKeys);

LinkedHashMap<Integer, Integer> sortedMap =
    new LinkedHashMap<>();

Iterator<Integer> valueIt = mapValues.iterator();
while (valueIt.hasNext()) {
    Integer val = valueIt.next();
    Iterator<Integer> keyIt = mapKeys.iterator();

    while (keyIt.hasNext()) {
        Integer key = keyIt.next();
        Integer comp1 = passedMap.get(key);
        Integer comp2 = val;

        if (comp1.equals(comp2)) {
            keyIt.remove();
            sortedMap.put(key, val);
            break;
        }
    }
}
return sortedMap;
}
   public static void main(String args[])
    {
      HashMap<Integer,Integer> hs = new HashMap<Integer,Integer>();
      int a[]={3,4,3,2,3,5,4,2,2,1,2};
       int n= a.length;
       int c=0;
       for(int i=0;i<n;i++)
        {
        if(hs.containsKey(a[i]))
        {
            c=hs.get(a[i]);
            hs.put(a[i],c+1);
        }
        else
        hs.put(a[i],1);
    }
     hs=Sum_of.sortHashMapByValues(hs);
    System.out.println(hs.keySet());
      }
 }