Leetcode #448 找到所有数组中消失的数字

目录

• 题目描述
• 解题思路
• 我的代码
• 心得

题目描述

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

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array

示例1：

输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
解释：1到8中，数组内没有出现5和6.
           

解题思路

关键词：

• 不使用额外空间且时间复杂度为O(n)，且返回的数组不算在额外空间内。
• 1 ≤ a[i] ≤ n ( n = 数组大小 ) 。

可利用的信息： 位置i 与 位置i对应的数值a[i]。

思路：

• 对已经存在的数a[i]做出一定的处理。
• 再通过该处理方式所对应的区分条件，挑出消失的数。

即：如果位置 t 对应的数a[t]没有被处理，则a中不存在数字 t+1。a[0]没被处理，则不存在数字1。

处理方式：

• 有数字Q，则将Q - 1 位置的数 + len(a)
• 比如：a中有数字 1，则将a[0]加上一个数。为方便判断，加上的这个数设为len(a)。

区分条件：

• 因为加上了数组的长度，且1 ≤ a[i] ≤ n ( n = 数组大小 )。那么可以说处理之后，

  消失的数 <= len(a)

  ，而

  存在的数 > len(a)

  。

我的代码

class Solution(object):
    def findDisappearedNumbers(self, nums):
        N = len(nums)
        for i in nums:
            nums[(i - 1) % N] += N
        return [i + 1 for i, num in enumerate(nums)if num <= N]
           

心得

• 本题类似散列表（哈希表），对判断列表中存在与否的题，可通过此方法减小空间。