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

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_)