給定一個(gè)范圍在??1 ≤ a[i] ≤ n (?n = 數(shù)組大小 ) 的 整型數(shù)組，數(shù)組中的元素一些出現(xiàn)了兩次，另一些只出現(xiàn)一次。

找到所有在 [1, n] 范圍之間沒有出現(xiàn)在數(shù)組中的數(shù)字。

您能在不使用額外空間且時(shí)間復(fù)雜度為O(n)的情況下完成這個(gè)任務(wù)嗎? 你可以假定返回的數(shù)組不算在額外空間內(nèi)。

示例:

輸入:
[4,3,2,7,8,2,3,1]

輸出:
[5,6]

我們可以用下標(biāo)對應(yīng)位置的正副來記錄某個(gè)數(shù)字有沒有出現(xiàn)過。

處理完后。

比如下標(biāo)為0的位置數(shù)字為-4，說明1這個(gè)數(shù)字出現(xiàn)過。

比如下標(biāo)為1的位置數(shù)字為3，說明2這個(gè)數(shù)字沒出現(xiàn)過。

class Solution {public List<Integer> findDisappearedNumbers(int[] nums) {for (int i = 0; i < nums.length; i++) {int index = Math.abs(nums[i]) - 1;//去對應(yīng)下標(biāo)做標(biāo)記。if (nums[index] > 0) {nums[index] *= -1;}}List<Integer> result = new LinkedList<Integer>();for (int i = 1; i <= nums.length; i++) {//大于0說明沒有出現(xiàn)過。if (nums[i - 1] > 0) {result.add(i);}}return result;} }

?

總結(jié)

以上是生活随笔為你收集整理的leetcode448. 找到所有数组中消失的数字 天秀记录法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。