# 448. Find All Numbers Disappeared in an Array

## 題目敘述

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`.

Example 1:

``````Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
``````

Example 2:

``````Input: nums = [1,1]
Output: [2]
``````

Constraints:

• `n == nums.length`
• `1 <= n <= 10**5`
• `1 <= nums[i] <= n`

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

## 解法解析

``````[1, 1, 3]

``````

### 解法範例

#### Go

##### Using Hash Map
``````func findDisappearedNumbers(nums []int) []int {
var hashTable = make(map[int]bool)

for _, num := range nums {
hashTable[num] = true
}

var result []int
for i := 1; i <= len(nums); i++ {
if _, ok := hashTable[i]; !ok {
result = append(result, i)
}
}
return result
}
``````
##### O(1) Space InPlace Modification Solution
``````func findDisappearedNumbers(nums []int) []int {
for _, num := range nums {
var newIndex int = num
if num < 0 {
newIndex = -num
}
newIndex--

if nums[newIndex] > 0 {
nums[newIndex] *= -1
}
}

var result []int
for i, num := range nums {
if num > 0 {
result = append(result, i+1)
}
}
return result
}
``````

#### JavaScript

##### Using Hash Map
``````/**
* @param {number[]} nums
* @return {number[]}
*/
var findDisappearedNumbers = function (nums) {
const hashTable = {};

for (const num of nums) {
hashTable[num] = true;
}

const result = [];

for (let i = 1; i <= nums.length; i++) {
if (!hashTable[i]) {
result.push(i);
}
}
return result;
};
``````
##### O(1) Space InPlace Modification Solution
``````/**
* @param {number[]} nums
* @return {number[]}
*/
var findDisappearedNumbers = function (nums) {
for (const num of nums) {
let newIndex = Math.abs(num) - 1;

if (nums[newIndex] > 0) {
nums[newIndex] *= -1;
}
}

const result = [];

for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
result.push(i + 1);
}
}
return result;
};
``````

#### Kotlin

##### Using Hash Map
``````class Solution {
fun findDisappearedNumbers(nums: IntArray): List<Int> {
var hashTable = HashMap<Int, Int>()
for (num in nums) {
hashTable[num] = 1
}

var result = ArrayList<Int>()
for (i in 1..nums.size) {
if (!hashTable.containsKey(i)) {
}
}
return result
}
}
``````
##### O(1) Space InPlace Modification Solution
``````class Solution {
fun findDisappearedNumbers(nums: IntArray): List<Int> {
for (i in nums.indices) {
val index = Math.abs(nums[i]) - 1
if (nums[index] > 0) {
nums[index] = -nums[index]
}
}

val result = mutableListOf<Int>()
for (i in nums.indices) {
if (nums[i] > 0) {
}
}

return result
}
}
``````

#### PHP

##### Using Hash Map
``````class Solution
{

/**
* @param Integer[] \$nums
* @return Integer[]
*/
function findDisappearedNumbers(\$nums)
{
\$hashTable = [];
foreach (\$nums as \$num) {
\$hashTable[\$num] = 1;
}

\$result = [];
for (\$i = 1; \$i <= count(\$nums); \$i++) {
if (!isset(\$hashTable[\$i])) {
\$result[] = \$i;
}
}
return \$result;
}
}
``````
##### O(1) Space InPlace Modification Solution
``````class Solution
{

/**
* @param Integer[] \$nums
* @return Integer[]
*/
function findDisappearedNumbers(\$nums)
{
foreach (\$nums as \$num) {
\$index = abs(\$num) - 1;
\$nums[\$index] = -abs(\$nums[\$index]);
}

\$result = [];
foreach (\$nums as \$i => \$num) {
if (\$num > 0) {
\$result[] = \$i + 1;
}
}
return \$result;
}
}
``````

#### Python

##### Using Hash Map
``````class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
"""
:type nums: List[int]
:rtype: List[int]
"""

# Hash table for keeping track of the numbers in the array
# Note that we can also use a set here since we are not
# really concerned with the frequency of numbers.
hash_table = {}

# Add each of the numbers to the hash table
for num in nums:
hash_table[num] = 1

# Response array that would contain the missing numbers
result = []

# Iterate over the numbers from 1 to N and add all those
# that don't appear in the hash table.
for num in range(1, len(nums) + 1):
if num not in hash_table:
result.append(num)

return result
``````
##### O(1) Space InPlace Modification Solution
``````class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
"""
:type nums: List[int]
:rtype: List[int]
"""

# Iterate over each of the elements in the original array
for num in nums:

# Treat the value as the new index
new_index = abs(num) - 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, num in enumerate(nums):
if num > 0:
result.append(i + 1)

return result
``````

#### Rust

``````
``````

#### Swift

##### Using Hash Map
``````class Solution {
func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
var hashTable: [Int: Bool] = [Int: Bool]()
for num: Int in nums {
hashTable[num] = true
}

var result: [Int] = [Int]()
for i: Int in 1...nums.count {
if hashTable[i] == nil {
result.append(i)
}
}
return result
}
}
``````
##### O(1) Space InPlace Modification Solution
``````class Solution {
func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
var nums: [Int] = nums
for i: Int in nums {
nums[i - 1] = -abs(nums[i - 1])
}

var result: [Int] = [Int]()
for (i, num) in nums.enumerated() {
guard num < 0 else {
result.append(i + 1)
continue
}
}

return result
}
}
``````