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

Question

给定整数的数组/列表，输出重复项。

此外，我真正在寻找的是:哪些解决方案具有最佳时间性能？最佳空间表现？有没有可能同时拥有最好的时间和最好的空间表现？只是好奇。谢谢!

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

Answer 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)因为没有创建额外的空间来产生重复

注意:重复数组的空间不能包含在空间复杂度方程中，因为这是我们想要的结果。

你能想到更多吗？