arrays - LeetCode 查找数组中所有消失的数字问题

Question

我正在做的问题陈述如下:

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

我找到了一个相当快地占用 O(n) 空间的解决方案，但是这个问题有一个找到恒定空间解决方案的条件，并且我不理解给出的解决方案。此处重新创建恒定空间解决方案，如下所示:

    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
                
        # Iterate over each of the elements in the original array
        for i in range(len(nums)):
            
            # Treat the value as the new index
            new_index = abs(nums[i]) - 1
            
            # Check the magnitude of value at this new index
            # If the magnitude is positive, make it negative 
            # thus indicating that the number nums[i] has 
            # appeared or has been visited.
            if nums[new_index] > 0:
                nums[new_index] *= -1
        
        # Response array that would contain the missing numbers
        result = []    
        
        # Iterate over the numbers from 1 to N and add all those
        # that have positive magnitude in the array 
        for i in range(1, len(nums) + 1):
            if nums[i - 1] > 0:
                result.append(i)       
        return result     

我不明白这段代码是如何工作的。对我来说，似乎每个元素在第一遍中都会被设为负数，因此不会将任何值附加到答案列表中。我通过调试器运行它，似乎并不是发生了什么。我希望有人能向我解释它在做什么。

Answer 1

举个例子:

nums = [4,3,2,7,8,2,3,1]

现在让我们迭代它，

Index-1: Value = 4 -> 将 (Value - 1) -> (4-1) 索引元素标记为负，前提是该元素为正。

现在，nums = [4,3,2,-7,8,2,3,1]

在此对每个索引执行此操作，

你会看到这个:

nums = [-4,-3,-2,-7,8,2,-3,-1]

索引 = 4 和索引 = 5 处的元素为正。

所以，答案是 [4+1,5+1] = [5,6]。

---

希望你明白这一点🔑。