找到所有数组中消失的数字

Leetcode Link: 448. 找到所有数组中消失的数字 - 力扣（LeetCode） (leetcode-cn.com)

题目

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

进阶：你能在空间空间 $O(1)$且时间复杂度为 $O(n)$ 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

解法一

思路：类似计数排序的思想，弄一个数组表示次数 需要注意 val 和 idx 的关系

哈希表也可以做，跟思路差不多，python中可以直接用集合set()来做

题解：时间空间都是 $O(N)$

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        '''
        类似计数排序, 注意 val 和 index 的关系        
        '''
        bucket = [0] * len(nums)
        for val in nums:
            bucket[val-1] += 1
        res = []
        for idx in range(len(bucket)):
            if bucket[idx] == 0:
                res.append(idx + 1)
        return res

解法二

思路：不借助额外的数据结构，依靠有限的变量进行原地操作。可以将重复的抹成 inf，然后检测 inf

这个判断的顺序是很重要的，如果顺序不对，那么输出就会有错误

题解：时间 $O(N)$, 空间 $O(1)$

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        '''原地把这个nums当成计数的bucket, 不存在的抹成inf'''
        idx = 0
        # 循环中可能执行的次数超过len(nums)次，但是肯定能出来
        # 想象如果nums所有的元素已经满足要求，那么就一定会走出来
        while(idx < len(nums)):
            val = nums[idx]
            if idx == val-1: 
	            #两个索引是同一个，说明位置正确，不操作
                idx += 1
            elif nums[idx]==float('inf'):
	            # 来过了，不操作
                idx += 1
            elif nums[idx] == nums[val-1]: 
	            # 这是重复的元素，把当前的变成inf，早晚换到缺的位置上
                nums[idx] = float('inf')
                idx += 1
            elif nums[idx] != nums[val-1]:
	            # 两者不相等，交换，此时idx可能没有看过换过来的值，因此idx不变
                nums[idx], nums[val-1] = nums[val-1], nums[idx]
 
		# 找结果
        res = []
        for idx in range(len(nums)):
            if nums[idx] == float('inf'):
                res.append(idx+1)
        return res