python-在整数数组/整数列表中查找重复项

给定整数数组/列表,输出重复项.

另外,我真正想要的是:哪些解决方案具有最佳的时间性能?最佳空间表现?是否可以同时拥有最佳时间和最佳空间性能?只是好奇.谢谢!

例如:给定列表[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])