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

沒有留言:

張貼留言