基於頻率的排序

給出一個整數數組，並根據其出現頻率
對這些整數進行排序。設計算法並分析其時間複雜度。在綁定的情況下，較小的
號碼應該首先出現在排序列表中。基於頻率的排序

樣品輸入：3,4,3,2,3,5,4,2,2,1,2
樣本輸出：1 5 4 3 2

2009-11-28 Tanuj

這聽起來像是一個家庭作業問題......是嗎？ – jheddings 2009-11-28 05:29:51

這絕對是一個家庭作業問題。 – 2009-11-28 09:21:33

這不是一個家庭作業問題。這個問題有很多實際的應用，例如你可能想要根據它們出現的次數來排序一個單詞列表（例如根據它們的流行度） – Tanuj 2009-11-28 14:58:11

如果額外的空間被允許：在去輸入並進行頻率分析。把它寫在一些哈希表中。這意味着，大致爲：

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是數字的頻率。

來源

2009-11-28 05:30:56

我曾考慮過這個問題，但是在使用散列表時我們必須注意碰撞。另外你將如何做一個Quicksort只在獨特的價值觀？在進行頻率分析時，您需要在某處存儲唯一值。 – Tanuj 2009-11-28 15:08:57

如果你有一個正常的散列表實現方便，碰撞沒有問題。如果表格不太小，則整個插入的運行時間將爲O（N）。至於唯一值 - 它們可以通過線性遍歷散列表中的所有鍵來獲得。 – 2009-11-28 15:50:36

如果這真的不是功課，請下載GLib。它有一個很好的哈希表實現，您可以使用 – 2009-11-28 15:51:13

排序數組，然後我們可以很容易地得到數字的頻率，因爲重複的數字將被放置在彼此相鄰。當你得到這些數字的頻率時，將它插入一個帶有鍵的映射中，頻率和值與數字一樣。由於地圖以排序順序存儲密鑰，因此我們可以迭代地圖以獲取結果。

來源

2010-10-26 05:07:11 San

如果多個數字具有相同的頻率，則此方法會失敗，因爲較舊的相同頻率數將被地圖中較新的一個替換。 **至於同一個鍵（頻率），會有多個值（數字）。** – 2015-08-04 11:06:00

@Abhinavkumar在這種情況下它會失敗。我們可以通過將映射值作爲int的向量而不是int來解決這個問題。 – San 2015-08-14 14:41:48

首先製作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()); 
     } 
}

來源

2016-11-04 16:06:32 ShreePool

基於頻率的排序

回答

相關問題