给定一个array/list
的integers
,输出的重复。
另外,我真正想要的是:哪种解决方案具有最佳的时间性能?最佳空间表现?是否可以同时拥有最佳的时间和最佳的空间性能?只是好奇。谢谢!
例如:给定list [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])
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句