［抄題］：

Given an array of integers where 1 ≤ a[i] ≤?n?(n?= size of array), some elements appear twice and others appear once.

Find all the elements of [1,?n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input: [4,3,2,7,8,2,3,1]Output: [5,6]

?[暴力解法]：

時間分析：

空間分析：

?[優化后]：

時間分析：

空間分析：

［奇葩輸出條件］：

［奇葩corner case］：

［思維問題］：

不知道怎么去除重復

［一句話思路］：

nums[nums[i] -1] = -nums[nums[i]-1] 每個數字處理一次。沒有被處理的正數就是被前面的擠兌了。背吧

［輸入量］：空：?正常情況：特大：特小：程序里處理到的特殊情況：異常情況（不合法不合理的輸入）：

［畫圖］：

［一刷］：

要做index的數必須取絕對值

［二刷］：

［三刷］：

［四刷］：

［五刷］：

? [五分鐘肉眼debug的結果]：

［總結］：

沒有被處理的正數就是被前面的擠兌了.這題[1,n]兩端必有的情況太特殊了

［復雜度］：Time complexity: O(n) Space complexity: O(1)

［英文數據結構或算法，為什么不用別的數據結構或算法］：

［關鍵模板化代碼］：

［其他解法］：

［Follow Up］：

［LC給出的題目變變變］：

442.?Find All Duplicates in an Array 出現兩次的：還是考數學啊

?[代碼風格] ：

class Solution {public List<Integer> findDisappearedNumbers(int[] nums) {//iniList<Integer> result = new ArrayList<Integer>();//ccif (nums == null || nums.length == 0) {return result;}//-1for (int i = 0; i < nums.length; i++) {int val = Math.abs(nums[i]) - 1;//trueif (nums[val] > 0) {nums[val] = - nums[val];}}//checkfor (int i = 0; i < nums.length; i++) {if (nums[i] > 0) {result.add(i + 1);}}//returnreturn result;} } View Code

?

轉載于:https://www.cnblogs.com/immiao0319/p/8870388.html

總結

以上是生活随笔為你收集整理的448. Find All Numbers Disappeared in an Array 寻找有界数组[1,n]中的缺失数的全部內容，希望文章能夠幫你解決所遇到的問題。

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