给定一个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