查找號碼重複k次未排序數組

-3

我們有一個包含整數的數組，我想在這個數組中找到重複k次的數字。該數組沒有排序，並且數字沒有限制。查找號碼重複k次未排序數組

實施例，

A（20，6，99，3，6，2，1,11,41，31，99，6，7，8，99，10，99，6）

查找重複超過3次的數字。

答：6,99

可能的答案使用逐位運算（XOR）或組合？運行時間效率Big（o）是必需的，以及空間容量。

這不是家庭作業，它只是一個有趣的問題。

O（n）時間和空間是否「高效」？ O（n lg n）時間和O（1）空間怎麼樣？兩種算法都會出現簡單的算法。通常，完美是善的敵人。最好有一個簡單的方法，而不是一個最佳但不可理解的方法。 – Patrick87 2013-02-15 15:08:48

在我的研究中，我還沒有遇到過這樣的問題，所以我無法判斷N lg N是否有效。但肯定O（1）在太空中。你爲了得到n lg n而對問題的處理方法是什麼？ – 2013-02-15 15:14:30

使用in-place O（n lg n）排序對數組進行排序，然後查找運行k或更多的某個元素？你只需要用計數器來運行排序後的數組;如果你有三個，打印出你在看什麼;如果您正在查看的內容發生更改，請將計數器重置爲1. – Patrick87 2013-02-15 15:19:28

Patrick87可能在評論中有最直接的答案，所以我會給出另一種方法。當您迭代您的列表時，您將同時創建一個元素（id，value）並在其中插入一個元素（id，value），其中id等於數字，並且該值與插入時初始化爲1的計數相匹配。如果該值已經存在於地圖中，則只需增加計數器。

插入到地圖中將需要O（log k）時間，其中k是地圖的大小。因此，您的總映射創建時間爲O（n log n）。

創建地圖之後，您可以遍歷它並輸出count ==目標計數的任意數字。

時間複雜度= O（N）+ O（N log n）的+ O（n）的= O（N log n）的空間複雜性= O（N）+ O（n）的= O（N）

如果你正在尋找更好的空間複雜性，你不會得到它......即使從流中讀取數字，你也需要跟蹤個別值爲O（n）的值。

2013-02-15 16:02:34 AndyG

回答