在字符和整數中找到第k個非重複元素（大尺寸）

Question

這是我在互聯網上發現的一個問題，在採訪中被問到。

給定一個非常大的字符和整數數組，我們必須找到第K個非重複元素。
例如：如果數組是{1,2，a，s，2，s，b，v}
並且如果K = 3
那麼答案應該是'b'。

需要約束：O(N)時間和O(1)空間。

我做了什麼？

我能想出的最佳解決方案是製作大小爲256的數組，並在元素出現時對其進行散列處理。
我認爲這是一個有效的解決方案，因爲數組256的大小與輸入數組大小無關。

我也嘗試過使用Kth-order statistics的方法，但是不能形成一個算法，因爲很多數字可以在第k個必需元素前後重複，所以無法確定它的位置。

我需要什麼？

請分享你的觀點，你將如何處理它。
我不想要任何代碼。

Answer 1

僅當您將字母表視爲常量大小時，您的方法才能正常工作，例如對於unicode32將會失敗。

但請注意，由於這是element distinctness problem的變體 - 我相信這個問題在時間和空間限制內無法解決。

證明：
假設你有一個使用「真實」 O(1)空間，O(n)時間這樣的算法。讓這個算法是A。
給定元素清晰度問題的一個實例，arr - 使用A(arr,n)。算法應返回arr[n]（1基礎），當且僅當數組中的每個元素都是唯一的。由於A是O(n)時間和O(1)空間 - 我們解決了O(n)時間和O(1)空間中的元素清除問題。