LeetCode 解題練習：Find All Numbers Disappeared in an Array

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

中文描述

給定一個含有[1, n] 之間的n個元素之整數陣列 nums (陣列長度為 n)，找出[1, n] 之間沒有出現在 陣列 nums 元素中的整數。 

範例一：

輸入 nums = [2, 2] 

輸出 [1]

範例二：

輸入 nums = [1, 2, 2] 

輸出 [3]

範例三：

輸入 nums = [1, 2, 1, 2, 1, 3, 4] 

輸出 [5, 6, 7]

解法一：

使用計數的方式記錄[1,n]每一個數字出現在 nums 的次數，再統計出現次數為0的數字有哪些。

Python Code

class Solution:

    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:

        n = len(nums)

        counts = [0] * n # 計算 [1,n] 數字出現的次數

       

        for i in nums:

            counts[i - 1] += 1 # 出現一次就增加1

       

        missingNumbers = [] # 沒出現在 nums 的數字

       

        for i in range(n):

            if counts[i] == 0: # 若出現次數為0次

                missingNumbers.append(i+1) # 加入到未出現之數字清單

       

        return missingNumbers

解法二：

使用不包含重複資料的資料結構，例如集合 set、字典 dictionary 來存放 nums 陣列中的數字，再找出沒有出現的數字。 

Python Code

class Solution:

    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:

        uniquedNumbers = set(nums) # 去除重複的數字

        disappearedNumbers = [] # 存放 [1, n] 中沒有在 nums 出現的數字

        for n in range(1, len(nums) + 1): # 走訪 [1,n] 數字

            if n not in uniquedNumbers: # 若沒有出現在 nums 中

                disappearedNumbers.append(n) # 加入沒有出現的數字清單中

       

        return disappearedNumbers

解法三：

讓有出現在 nums 的數字 i ，當成索引後，變更 nums[i] 為有負號，在統計 nums[i] 中有哪些 nums[i] 值為大於零，i 值為未出現在 nums 的數字。

Python Code

class Solution:

    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:

       

        for i in nums:

            idx = abs(i) - 1 # 索引為 i 之正值減去 1

            if nums[idx] > 0: # 若大於零

                nums[idx] = -nums[idx] # 變成負數， i 標記為有出現

       

        missingNumbers = [] # 沒出現在 nums 的數字

       

        for i in range(len(nums)):

            if nums[i] > 0: # 若大於零，代表 i 未出現在 nums 中

                missingNumbers.append(i+1) # 加入到未出現之數字清單

       

        return missingNumbers