448. 找到所有数组中消失的数字

Posted on Edited on In , ,
转载自Leet Code

题目描述

给定一个范围在 $ 1 ≤ a[i] ≤ n$ ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。 找到所有在 \([1, n]\) 范围之间没有出现在数组中的数字。 您能在不使用额外空间且时间复杂度为\(O(n)\)​的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例 1： 输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6]

示例 2：

输入：nums = [1,1] 输出：[2]

提示：

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n

我的代码

\(T(N) = O(N)\), \(S(N) = O(N)\)

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class MySolution448 
{
    public List<Integer> findDisappearedNumbers(int[] nums) 
	{
    	HashSet<Integer> set = new HashSet();
    	for (int i=0; i<nums.length; i++)
    		set.add(nums[i]);
    	
    	LinkedList<Integer> list = new LinkedList();
    	for (int i=0; i<nums.length; i++)
    	{
    		if (!set.contains(i+1))
    			list.add(i+1);
    	}
    	return list;
    }
}

方法：原地修改

\(T(N) = O(N)\), \(S(N) = O(1)\)

我们可以在输入数组本身以某种方法标记已经访问过的数字，然后再去找到缺失的数字。 （利用了数组下标与数组中应有元素之间的关系）

首先遍历一次数组，将索引\(|nums[i]|-1\)处的元素设置为其负值， 即 \(nums[|nums[i]|-1] ×= -1\); 注意如果已经是负值则说明这个元素已经标记过了，略过； 然后再遍历一次数组，若发现元素nums[i]仍为正数则说明其对应下标i+1是缺失的数字。

代码

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution448 
{
    public List<Integer> findDisappearedNumbers(int[] nums) 
	{
    	LinkedList<Integer> list = new LinkedList();
    	for (int i=0; i<nums.length; i++)
		    // 如果已经<0则说明这个元素已经出现过（标记过）了
    		if (nums[Math.abs(nums[i])-1]>0)
    			nums[Math.abs(nums[i])-1] *= (-1);
    	
    	for (int i=0; i<nums.length; i++)
    		if (nums[i]>0)
    			list.add(i+1);
    	
    	return list;
    }
}