Сортировка по частоте

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) 

Тогда простой Quicksort на уникальных значений, с функцией сравнения с учетом частоты вместо самого значения.

То есть:

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

compare Где числовой для частот.

Answer 2

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

Answer 3

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

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