在O（n）時間估計一個數組元素的頻率

Question

我想標題可能有點誤導，但我想不出一個更好的。 我有一個數組A []，其中的所有元素都出現了一些倍數爲15的倍數，例如2次發生30次，3次發生45次。但是一個元素會出現x次，其中x不是15的倍數。如何打印數字x。我正在尋找一個沒有散列表的線性解決方案。

謝謝。

Answer 1

這裏有類似的問題，在StackOverflow上，但我找不到它。

讓我們使用3而不是15，因爲它會更容易，我認爲它是完全等效的。序列將是4, 5, 4, 5, 3, 3, 4, 5，二進制100, 101, 100, 101, 11, 11, 100, 101。

你可以做到以下幾點：和所有的值在至少數顯著位和取餘數比3（15最初）：

bit1 = (0 + 1 + 0 + 1 + 1 + 1 + 0 + 1) % 3 = 5 % 3 = 2 != 0

如果!= 0那麼該位等於1我們試圖找到的數字。現在讓我們移動到下一個：

bit2 = (0 + 0 + 0 + 0 + 1 + 1 + 0 + 0) % 3 = 2 % 3 = 2 != 0

bit3 = (1 + 1 + 1 + 1 + 0 + 0 + 1 + 1) % 3 = 6 % 3 = 0 == 0

因此，我們必須bit3 == 0, bit2 != 0, bit1 != 0，使得011。轉換爲十進制：3。

空間複雜度爲O(1)和時間複雜度爲O(n * BIT_LENGTH_OF_VARS)，其中BIT_LENGTH_OF_VARS == 8爲字節，BIT_LENGTH_OF_VARS == 32對於int等，因此，它可以很大，但常數不影響漸近性和O(n * BIT_LENGTH_OF_VARS)真的O(n)。

就是這樣！