Намиране на дубликати в масив / списък на числа - питън, масиви, алгоритъм, списък, сортиране

Като се има предвид 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

Отговори:

Един начин да получите дубликата:

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])

Намирането на дубликати е много подобно на сортирането. Това означава, че всеки елемент трябва да бъде пряко или непряко сравнен с всички други елементи, за да се намери, ако има дубликати. Би могло да се модифицира бързодействащ към изходен елемент, който има съседен съвпадащ елемент с O (n) пространствена сложност и O (n * log (n)) средна времева сложност.

Има множество решения за намиране на дубликати. Като се има предвид, че този въпрос е напълно родов, може да се предположи, че е даден списък с 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) да преминете през всички стойности
   • Space: 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) за сортиране и преместване на всички стойности
   • Space: 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) Space: O(1) като никакво допълнително пространство, създадено да произвежда дубликати

Забележка: пространството за дублирания масив не може да бъде включено в уравненията на пространствената сложност, тъй като това е резултатът, който искаме.

Можете ли да се сетите за още нещо?