从数组中不存在的集合中查找数字

Question

我在一次采访中被问到这个问题：给你一组数字{1..N}和一个数组a[N-1]。从数组中不存在的集合中查找数字。下面是到目前为止我所拥有的代码和伪代码，它们都不起作用

我假设集合中有一个（并且只有一个）数字不在数组中

1. 循环遍历集合中的每个元素
2. 循环遍历数组中的每个元素O（n）
3. 检查该数字是否在数组中
4. 如果是，什么也不做
5. 否则，请提前返回号码

def findMissingNo(arr, s):  
    for num in s: #loop through each element in the set
        for num2 in arr: ##loop through each element in the array O(n)
            if (num == num2): #if the number in the set is in the array, break 
                break
        print (num)
        return num #if the number in the set is not in the array, early return the number 
    return -1 #return -1 if there is no missing element 

s1 = {1,4,5}
arr1 = [1,4]

findMissingNo(arr1, s1)

Answer 1

根据定义，我们有一个从1到N的集合和一个大小为N-1的数组，包含从1到N的数字，缺少一个数字，我们必须找到那个数字

因为只缺少1个数字，集合有n个元素，数组有n-1个元素。所以数组是集合的子集，缺少的元素就是缺少的，这意味着

all_number_of_set = all_number_of_array + missing_number

也

sum_of_all_number_of_set = sum_of_array_number + missing_number

这意味着

missing_number = sum_of_all_number_of_set - sum_of_array_number

伪码

def findMissingNo(set_, arr_ ):
      return sum(set_) - sum(arr_)

Answer 2

您的函数是二次函数，因为它必须检查集合中每个项目的整个列表

不要在集合上迭代，这一点很重要。是的，这是可行的，但是您不知道在python（或一般的哈希表）中可以从set或dict中获得的时间复杂性优势。但是您也不能遍历列表，因为缺少的项是。。。丢失的所以你在那里找不到它

相反，您可以从列表中构建一个集合，并使用差分函数。或者更好的是，对称差（^）见https://docs.python.org/3.8/library/stdtypes.html#set

def findMissingNo(arr, s):        
    d = set(arr) ^ s # symmetric difference
    if 1 == len(d):
        for item in d:
            return item

print (findMissingNo([1,4], {1,4,5}))

5

我走了一些捷径，因为我知道我们想要一件物品，而且我知道它应该放在哪个容器中。如果没有找到任何项目，我决定不返回任何项目，但我没有检查多个项目

Answer 3

如果我很好地理解了你的问题，那么你正在找到一种有效的方法来查找set中不存在的list数。我看到你是内部循环，这将是O(n^2)。我建议为list创建dict，它将是O(n)，然后通过循环set{}在dictionay中找到O(1)元素。考虑到具有子集set的大型list：

def findMissingNo(arr_list, s_list):
    d = dict()
    for el in arr_list:
        d.update({el: el})
    for s in s_list:  
        try:
            d[s]
            pass
        except KeyError:
            return s
    return -1 

s1 = {1,4,5}
arr1 = [1,4]

findMissingNo(arr1, s1)

希望有帮助：）