編寫一個算法來查找數組中最常出現的元素。給算法的時間複雜性

-4

我在'算法分析'的任務上工作，我堅持這個問題，我必須明天提交它，我需要幫助。請回答你是否可以解決這個問題。編寫一個算法來查找數組中最常出現的元素。給算法的時間複雜性

給定一個n個數的數組A，編寫一個有效的算法來查找該數組中最常出現的元素（該數組的模式）。還要分析您的算法的時間複雜度。

你到目前爲止做了什麼？ – 2014-11-25 12:37:11

我開發了一種算法，每次元素髮生時都會進行計數，然後對其進行比較。但是效率不高。 – 2014-11-25 12:39:43

@DaimShahzad至少顯示你當前的結果。但我認爲這將會更適合計算機科學stackexchange網站之一。 – stefan 2014-11-25 12:42:29

由於這是一項任務，我只會給你一個關於複雜性上限和類似問題的提示。

這個問題比Element Distinctness Problem 更困難。已知元素清晰度問題不能比O(nlogn)最差的情況更好地解決。爲元素清晰度的解決方案是：

排序和迭代 - O(nlogn)
創建元素的集合/直方圖和檢查uniqeness。這是通過使用hashtables在O(n)平均情況下和O(n^2)最壞情況和O(n)額外空間完成的。

想想這兩種方法，並嘗試考慮如何修改它們來解決您的問題。
此外，元素清晰度的下限告訴您不會有任何算法比O(nlogn)最壞的情況更好。

（1）元素區別問題：數組中的所有元素是否都是不同的？或者是否有任何元素也有其自身的副本？

2014-11-25 12:45:31 amit

@DaimShahzad如果所有的元素都是不同的，怎麼會有最頻繁發生的元素呢？顯然，所有的元素都發生相同的次數。 – stefan 2014-11-25 13:27:46

哦，對不起，這是另一個問題。所有元素都不明顯。 – 2014-11-25 13:43:54

回答