LeetCode第448题找到所有数组中消失的数字（Python）

题目描述

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例1:

输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题方法和思路

带*的表示参考其他人的实现

创建一个标记数组

思路:
非常简单，遍历一遍原数组，在标记数组对应位置记录是否出现过即可。
空间复杂度不满足题目要求，需要额外创建一个标记数组.
复杂度：

1. 时间复杂度：$O(n)$O(n)
2. 空间复杂度：$O(n)$O(n)

核心代码：

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        result = []
        mark_list = [0] * (len(nums)+1)
        mark_list[0] = 1
        for num in nums:
            mark_list[num] = 1
        for index, mark in enumerate(mark_list):
            if not mark:
                result.append(index)
        return result

利用原数组全部大于零的特性进行标记*

思路：
巧妙利用原数组全部大于零的特性，将列表元素所对应的列表索引的值置为负数来标记该索引对应的数值出现过，去索引时，只需做绝对值操作即可抵消前面的重置为负数的影响，可以做到不用额外的存储空间
代码:

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # 将所有正数作为数组下标，置对应数组值为负值。那么，仍为正数的位置即为（未出现过）消失的数字。
        # 举个例子：
        # 原始数组：[4,3,2,7,8,2,3,1]
        # 重置后为：[-4,-3,-2,-7,8,2,-3,-1]
        # 结论：[8,2] 分别对应的index为[5,6]（消失的数字）
        for num in nums:
            index = abs(num) - 1
            # 始终保持nums[index]为负数
            nums[index] = -abs(nums[index])
        return [i + 1 for i, num in enumerate(nums) if num > 0]

作者：gehui1007
链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/solution/ti-jie-bu-shi-yong-e-wai-kong-jian-by-gehui1007/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度：

1. 时间复杂度：$O(n)$O(n)
2. 空间复杂度：$O(1)$O(1)