LEETCODE 448.找到所有数组中消失的数字
题目描述
给定一个范围在 1 ≤ a[i] ≤ n
( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。
找到所有在 [1, n]
范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
题目地址:
https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
题解
注意题目要求不能使用额外空间
,这也是这道题的难点所在。
这道题里面其实包含了隐藏的条件,1 ≤ a[i] ≤ n
,即每个数字本身都对应一个i-1
的数组下标
。
我们可以利用数组内容本身跟数字下标的关联找出缺失的数字。
扫描两遍数组,第一次将所有数字做标记,第二次根据标记信息找出缺失的数字。下面来看详细分析。
假设有数组[1,2,3,4,5,6]
如下图:
数组上方的是数组的下标,通过这张图可以发现,数组中的每个值都有一个对应的数组下标,比如值为4的
对应下标3
。即arr[i]
对应i-1
如果数组是乱序的呢?
乱序的数组并不影响,比如值为3的
对应的是下标2
,值为6的
对应的是下标5
。
我们可以利用下标这个隐藏条件,再假设有下面数组,数组缺少5
因为每个arr[i]
都对应下标i-1
,我们将arr[i]
对应的下标中的数组值置为负,比如值是3的
对应下标2
,我们将arr[2]
中的值设置为arr[2]*=-1
。对[1,2,3,4,6,6]
这个数组我们做如下操作:
1=>arr[0]
,将arr[0]
设置成-1
2=>arr[1]
,将arr[1]
设置成-2
3=>arr[2]
,将arr[2]
设置成-3
4=>arr[3]
,将arr[3]
设置成-4
6=>arr[5]
,将arr[5]
设置成-6
6=>arr[5]
,将arr[5]
设置成-6
再扫描一遍数组,找到大于0
的数,这里是6
,它的数组下标是4
,但现在arr[4]
大于0,说明缺少数字5
,因为5
对应数组下标4
。
如果数组是乱序的,也不会影响其结果。
扫描一遍,仍然是下标4
大于0,即缺少数字5
。
如果用0作为标记呢?
这样是不行的,arr[0]=>2
,即将arr[1]
设置成了0
,这样就等于把已有的信息给覆盖了。
再看下题目中的列子,数组[4,3,2,7,8,2,3,1]
具体操作如:
4=>arr[3]
,将arr[3]
的值设置为-7
3=>arr[2]
,将arr[2]
的值设置为-2
2=>arr[1]
,将arr[1]
的值设置为-3
7=>arr[6]
,将arr[6]
的值设置为-3
8=>arr[7]
,将arr[7]
的值设置为-1
2=>arr[1]
,将arr[1]
的值设置为-3
3=>arr[2]
,将arr[2]
的值设置为-2
1=>arr[0]
,将arr[0]
的值设置为-4
经过转换得到新数组[-4, -3, -2, -7, 8, 2, -3, -1]
扫描一遍8
和2
大于0,他们分别对应下标4
和下标5
,所以缺失的数字是5
和6
。
复杂度分析
时间复杂度:O(n),扫描两边数组
空间复杂度:O(1)
java代码实现:
class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { List<Integer> res = new ArrayList<Integer>(); //第一遍扫描,根据数组的值找到对应的下标,比如3对应下标2 //将arr[2]设置成负数 for(int i=0;i<nums.length;++i) { int index = Math.abs(nums[i])-1; if(nums[index]>0) { nums[index] *= -1; } } //第二遍扫描,找到所有非负数,非负数所在的下标+1,即为缺失的数字 for(int i=1;i<=nums.length;++i) { if(nums[i-1]>0) { res.add(i); } } return res; } }
python代码实现:
class Solution(object): def findDisappearedNumbers(self, nums): """ :type nums: List[int] :rtype: List[int] """ res = [] # 第一遍扫描,根据数组的值找到对应的下标,比如3对应下标2 # 将arr[2]设置成负数 for i in xrange(len(nums)): index = abs(nums[i])-1 if nums[index]>0: nums[index] *= -1 # 第二遍扫描,找到所有非负数,非负数所在的下标+1,即为缺失的数字 for i in xrange(1,len(nums)+1): if nums[i-1]>0: res.append(i) return res
(全文完)
13 次阅读