在由一系列连续整数创建的列表中查找丢失的元素，在 O(n) 中具有重复项

Question

这是一个来自 LeetCode的Find All Numbers Disappeared in an Array问题：

给定一个整数数组，其中1 ? a[i] ? n (n = size of array)，某些元素出现两次，而其他元素出现一次。

查找所有[1, n]未出现在此数组中的inclusive元素。

你能在没有额外空间和 O(n) 运行时完成吗？您可以假设返回的列表不算作额外空间。

例子：

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

我的代码如下 - 我认为它是 O(N) 但面试官不同意

def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    results_list=[]
    for i in range(1,len(nums)+1):
        if i not in nums:
            results_list.append(i)
    return results_list

Answer 1

您可以实现一种算法，循环遍历列表的每个元素，如果列表包含元素 i 作为值之一，则将索引 i 处的每个元素设置为负整数。然后，您可以添加每个索引 i，该索引对您的缺失项目列表是正数。它不占用任何额外的空间，最多使用 3 个 for 循环（不嵌套），这使得复杂度为 O(3*n)，基本上是 O(n)。该网站对此进行了更好的解释，并且还提供了源代码。

编辑- 我添加了代码以防有人需要：

#The input list and the output list
input = [4, 5, 3, 3, 1, 7, 10, 4, 5, 3]
missing_elements = []

#Loop through each element i and set input[i - 1] to -input[i - 1]. abs() is necessary for 
#this or it shows an error
for i in input:    
    if(input[abs(i) - 1] > 0):
        input[abs(i) - 1] = -input[abs(i) - 1]
    
#Loop through the list again and append each positive value to output list
for i in range(0, len(input)):    
    if input[i] > 0:
        missing_elements.append(i + 1)