題目

給你一個含 n 個整數的數組 nums ，其中 nums[i] 在區間 [1, n] 內。請你找出所有在 [1, n] 范圍內但沒有出現在 nums 中的數字，并以數組的形式返回結果。
示例 1：
輸入：nums = [4,3,2,7,8,2,3,1]
輸出：[5,6]
示例 2：
輸入：nums = [1,1]
輸出：[2]
提示：
n == nums.length
1 <= n <= 10^5
1 <= nums[i] <= n
進階：你能在不使用額外空間且時間復雜度為 O(n) 的情況下解決這個問題嗎? 你可以假定返回的數組不算在額外空間內。
來源：力扣（LeetCode）

解題思路

??題目要求查找缺失的數字，首先可以準備一個完整的序列然后逐一對比序列中的值是否在nums中，如果不在則當前值便是缺失的值。這樣做的時間復雜度的量級便跑到了O(n^2)，所以需要先哈希一下原數組。

class Solution:def findDisappearedNumbers(self, nums: List[int]) -> List[int]:n=set(nums)temp=[]for i in range(1,len(nums)+1):if i not in n:temp.append(i)return temp

??另外題目給出了進階的建議，原地完成算法。想要原地空間就必須充分挖掘數組中的元素和下標的關系，在這個題目中，如果我們正常訪問能訪問到所有的元素，而我們以元素為下標訪問數組則會有重復訪問的和不能訪問到的元素，如果以顛倒元素值和下標為映射關系如何標記已經訪問過的元素呢？再開辟一個數組顯然不符合要求，直接訪問并修改元素值以用來標記又會影響后續的訪問?，F在似乎需要這樣的一個函數；當訪問前面元素的時候更改掉以當前元素為下標的元素的值，當訪問到被更改的元素的時候，能夠還原它原來的值以便找到真正的映射下標，也就是一個函數兩次作用于同一個數值是要能回到最初的狀態的，這樣的函數有求倒數，添負號，加一個足夠大的數然后再減去這個數，乘以一個足夠大的數然后再除以這個數…；求這個題不能用倒數，因為遇到1會有一些問題。由于這個題目最大值有上限，我們就利用加一個足夠大的數。

class Solution:def findDisappearedNumbers(self, nums: List[int]) -> List[int]:n=len(nums)+1  #設置足夠大的數for i in nums:  #對應的映射規則if i<n:if nums[i-1]<n:nums[i-1]+=nelse:if nums[i-1-n]<n:nums[i-1-n]+=ntemp=[]for i in range(len(nums)):if nums[i]<=len(nums):temp.append(i+1)return temp

總結

以上是生活随笔為你收集整理的LeetCode简单题之找到所有数组中消失的数字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。