# 448. Find All Numbers Disappeared in an Array 找到所有数组中消失的数字

@TOC

[LeetCode]

• Total Accepted: 14302
• Total Submissions: 24993
• Difficulty: Easy

## # 题目描述

Given an array of integers where `1 ≤ a[i] ≤ n` (n = size of array), some elements appear twice and others appear once.

Find all the elements of `[1, n]` inclusive that do not appear in this array.

Could you do it without extra space and in `O(n) `runtime? You may assume the returned list does not count as extra space.

Example:

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

Output: [5,6]
``````

## # 题目大意

### # 方法一：暴力求解

``````class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
cList = list(range(1, len(nums) + 1))
returnList = []
for x in nums:
cList[x - 1] = 0
for x in cList:
if x != 0:
returnList.append(x)
return returnList
``````

AC:359 ms

### # 方法二：原地变负做标记

``````class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
for i in range(len(nums)):
index=abs(nums[i])-1
nums[index]= - abs(nums[index])
return [i+1 for i in range(len(nums)) if nums[i] > 0]
``````

AC:362 ms

### # 方法三：使用set

Python代码如下，打败96%.

``````class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
res = []
numset = set(nums)
N = len(nums)
for num in range(1, N + 1):
if num not in numset:
res.append(num)
return res
``````

## # 日期

2017 年 1 月 2 日 2018 年 11 月 10 日 —— 这么快就到双十一了？？