整数の配列/リストで重複を見つける - Python、配列、アルゴリズム、リスト、ソート

与えられた array/list の integers複製を出力します。

また、私が本当に探しているのは、どのソリューションが最高の時間パフォーマンスを発揮するかということです。最高の宇宙パフォーマンス？最高の時間と最高のスペースパフォーマンスを両立させることは可能ですか？ちょっと興味があるんだけど。ありがとうございました！

例：与えられたリスト [4,1,7,9,4,5,2,7,6,5,3,6,7]答えは [4,7,6,5] （出力の順番は関係ありません）。

私は自分の解決策をに書いた。 python.

これが私がハッシュと二分探索を使って書いた一つの解決策です。

def binarySearch(array, number):
start = 0
end = len(array)
mid = (end + start) // 2
while (end > start):
mid = start + (end - start) // 2
if array[mid] == number:
return (mid, True)
elif number > array[mid]:
if start == mid:
return (mid + 1, False)
start = mid
else:
end = mid

return (mid, False)

def findDuplicatesWithHash(array):
duplicatesHash = {}
duplicates = []
for number in array:
try:
index,found = binarySearch(duplicates, number)
if duplicatesHash[number] == 0 and not found:
duplicates.insert(index, number)
except KeyError as error:
duplicatesHash[number] = 0

duplicatesSorted = sorted(duplicates, key=lambda tup: tup)
return duplicatesSorted

回答：

複製を取得する1つの方法：

l = [4,1,7,9,4,5,2,7,6,5,3,6]
import collections

print([item for item, count in collections.Counter(l).items() if count > 1])

重複を見つけることはソートと非常によく似ています。 つまり、重複があるかどうかを判断するには、各要素を他のすべての要素と直接または間接的に比較する必要があります。 Ｏ（ｎ）空間複雑度およびＯ（ｎ ＊ ｌｏｇ（ｎ））平均時間複雑度を有する隣接マッチング要素を有する出力要素へのクイックソートを修正することができる。

重複を見つける方法は複数あります。この質問は完全に一般的なものであると仮定すると、 n 値、重複数は範囲内 [0, n/2].

考えられる方法は何ですか？

1. ハッシュテーブルアプローチ：

   値がハッシュテーブルに存在しない場合は、リストを移動しながら値を保存します。値が存在する場合は、重複しています。

   Algorithm FindDuplicates(list)
   hash_table <- HashTable()
   duplicates <- List()
   for value in list:
   if value in hash_table:
   duplicates.add(value)
   else:
   hash_table.add(value, true)
   

   • 時間： O(n) すべての値を通過する
   • スペース： O(n) ハッシュテーブルにすべての可能な値を保存します。

2. ソート配列

   配列をソートし、隣接値を走査します。

   Algorithm FindDuplicates(list)
   list.sort()
   duplicates <- Set()
   for i <- [1, len(list)-1]:
   if list[i] = list[i-1]:
   duplicates.add(list[i])
   

   • 時間： O(n.logn) + O(n) = O(n.logn) すべての値をソートしてトラバースする
   • スペース： O(1) 複製を作成するために余分なスペースが作成されないため

3. すべての値を確認してください

   値ごとに、値が配列に存在するかどうかを確認します。

   Algorithm Search(i, list):
   for j <- [0, len(list)-1] - [i]:
   if list[j] = list[i]:
   return true
   return false
   
   Algorithm FindDuplicates(list)
   duplicates <- Set()
   for i <- [1, len(list)-1]:
   if Search(i, list):
   duplicates.add(list[i])
   

   時間： O(n^2) 比較数は n*n(-1) スペース： O(1) 複製を作成するために余分なスペースが作成されないため

注：重複配列のスペースは、スペース複雑度の式に含めることはできません。これが目的の結果です。

もう少し考えてもらえますか。