基於頻率的排序

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，將數組元素作爲關鍵字，並將它們的頻率作爲值。 根據鍵和值使用比較器對它們進行排序。

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