如何查找在O（1）空間和O（n）時間成本（帶有限元素尺寸）的未排序列表中出現k次的元素

Question

這不是問題，而是聚合帖子。我如何才能實現O（1）空間和O（n）時間複雜度操作某些值類型的項目（通常是整數或字符）列表，如果我要找到n次出現的元素，排序列表或找到所有唯一值？

一個小紙條。這僅適用於具有固定值範圍的值類型對象（例如整數，字符等）。

UPDATE

有許多有關使用這樣的方法來實現ö問題（1）的空間和O（n）的時間複雜度排序或搜索出現的k倍，或甚至數元素時時代，或獨特的元素左右。所以，請仔細閱讀的問題，尤其是第一條語句。這是一個FAQ風格的帖子，不是一個問題。

此外，我知道答案，不需要一次又一次地發佈。如果你覺得你可以添加一些有價值的東西 - 隨時編輯題目中的問題和最長的答案（請注意，它是我自己的回答），所以它成爲一個社區維基。

相關問題：

1. Finding the first non-repeated character of a string in O(n) using a boolean array?
2. Find a single integer that occurs with even frequency in a given array of ints when all others occur odd with frequency
3. Find if 2 strings are anagram in O(1) space and O(n) time
4. Finding duplicates in O(n) time and O(1) space
5. Find duplicates in an array
6. O(n) algorithm to find out the element appearing more than n/2 times

Answer 1

由於輸入大小有界，因此您可以簡單地在輸入上運行Counting Sort算法，然後查找結果。計數排序需要O（n），並且查找數組的特定元素具有特定的出現時間是排序數組中的O（n）。

Answer 2

其基本思想是O（1）的空間複雜度實際上意味着內存消耗獨立於數組的大小。

因此，如果您正在操作的陣列元素的範圍有限（例如-128..127），您可以分配長度爲max_value-min_value+1的散列狀數組以跟蹤每個值的出現次數（讓我們打電話它現在計數陣列）。

使用這樣的方法，你掃描陣列只有一次（因此O(n)時間複雜度），累積每個單獨的值的出現次數，最後你能回答以下問題：

1. 是否存在的元素奇數/偶數次出場？只有一個外觀？ 任意數字的出場？（只是掃描計數陣列）
2. 初始數組中出現的唯一值是什麼（選擇count-array中值大於1的所有鍵）
3. 對數組進行排序（有點複雜，請參閱示例以下）

終於在Python

import random, sys 
min_val = -5 
max_val = 5 
initial_array = [random.randint(min_val, max_val) for i in range (0,20)] 
count_array = {i:0 for i in range(min_val,max_val+1)} 

for elem in initial_array: 
    count_array[elem]+=1 

#print initial_array 

#1. Find unique values 
unique_values = [item for item, count in count_array.iteritems() if count>0] 
#print unique_values 

#2. Find n-time-appearing values 
n=2 
n_times_appear = [item for item, count in count_array.iteritems() if count==n] 
#print n_times_appear 

#3. Find odd times appearing numbers 
odd_times_appear = [item for item, count in count_array.iteritems() if not count%2] 
#print odd_times_appear 

#4. Sort an array 
#We don't actually sort an array - we just reconstruct it. 
sorted_array = [] 
for item,count in sorted(count_array.iteritems()): 
    for i in range(0,count): 
     sorted_array.append(item) 

#print sorted_array 

一些代碼樣本隨意添加其他語言的實現以及糾正我，如果我錯了:)

Answer 3

如果您使用稍微偷偷摸摸論證每個項目的唯一值的數量是固定的，那麼您可以爲每個唯一的值爲O（1）空間的哈希映射。

現在你的問題的答案是微不足道的。只需查看一次該列表並累計哈希映射中的出現次數。準時。

注意，回答提出的問題，不需要排序。