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

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]
扫描一遍82大于0,他们分别对应下标4下标5,所以缺失的数字是56

复杂度分析
时间复杂度: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
                                                                               

(全文完)

11 次阅读

发表评论

电子邮件地址不会被公开。