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.length1 <= n <= 10**51 <= 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, n] 的範圍內不包含的值有哪些。例如陣列長是 3，那就是 1~3 的值，有哪些不在陣列中。如果陣列是 [1, 1, 3]，那就會是 2。
解法解析
解法的重點不外乎就是要記住，哪些值已經檢查過。第一種解法就是使用 Hash Table 的方式來記錄哪些值已經檢查過了，但因為使用 Hash Table 空間複雜度的就比較高 O(n)。想要維持住 O(n) 的時間複雜度又要降低空間度雜度的話，就是會想到 In-place 了，所以第二個解法就是使用 In-place。
這邊 In-place 的解法是滿巧妙的運用，將值當作 Index 的方式。因為排序過後的話，該位置的值應該會相當於 index + 1 = value。將該值變成負值，最後查詢哪些 value 依舊是正數，那就知道了哪些值不存在。
[1, 1, 3]
遍歷 index = 0, value = 1 ==> [-1, 1, 3]
遍歷 index = 1, value = 1 ==> [-1, 1, 3], index 0 已經是負值，所以不變動
遍歷 index = 2, value = 3 ==> [-1, 1, -3]
剩下 index 2 是正數，所以不存在的值是 2
解法範例
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)) {
result.add(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) {
result.add(i + 1)
}
}
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
}
}