陣列中某個數字的頻率比線性時間快

Question

查找數組中的數字的頻率小於O（n）時間。

Array 1,2,2,3,4,5,5,5,2 
Input 5 
Output 3 

Array 1,1,1,1 
Input 1 
Output 4 

Answer 1

如果你有唯一信息是一個排序的數組（如您的測試數據似乎表明），你不能做得比O(n)找到一個給定值的頻率更好。沒有得到解決。

爲了達到更好的時間複雜度，有多種方法。

---

一個將保持數組排序（或如果你不想改變順序一個並行排序的數組）。這樣，您可以使用二進制搜索來查找具有給定值的第一個項目，然後順序掃描該部分以獲得計數。雖然最差的情況下（所有項目相同，並且該值是您要查找的）仍然是O(n)，它將傾向於O(log n)平均情況。

請注意，每次在查找值之前對數據進行排序將不起作用，因爲這幾乎肯定會推動您的超出的O(n)限制。這個想法是隻對物品插入進行排序。

---

如果您的域（可能的值）有限，另一種方法是單獨維護這些值的實際頻率。例如，如果域限制爲數字1到數百，則應該有一個單獨的數組，其中包含每個值的頻率。

當列表爲空時，所有頻率都爲零。無論何時添加或刪除項目，都會增加或減少該值的頻率。這將使得頻率提取成爲一個快速的操作。

---

但是，如前所述，這兩種解決方案都需要額外/修改數據來維護。沒有這一點，你不可能比O(n)做得更好，因爲你需要檢查數組中的每一項，看它是否與你正在查找的值相匹配。