攻城獅
Not a programmer 不工程的攻城獅

Not a programmer 不工程的攻城獅

LeetCode Solution, Easy, 448. Find All Numbers Disappeared in an Array

找尋陣列中所有消失的元素

攻城獅's photo
攻城獅
·May 30, 2022·

Subscribe to my newsletter and never miss my upcoming articles

Play this article

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, 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
    }
}

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this

Impressum

As smiple as possible