若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。
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
