算法小抄5-原地哈希
书接上回,学会了数组中重复数字的解法三,相信接下来的题也难不倒你
找到数组中消失的数字
题目链接
题意
对于一个大小为n的数组,数组中所有的数都在[1,n]内,其中有些数字重复了,由于有些数字重复了,另一些数字就一定会确实,这次需要找到所有缺少的数字并且返回结果
有没有发现,原地哈希的题目条件中总会带有大小为n,然后再限制每个数的范围,在之前的数组题中限制的是[0,n-1]这次的题限制的是[1,n]
例子
对于数组[4,3,2,7,8,2,3,1],我们根据原地哈希的规则将该数组重写排列,将下标与值对应,即值=下标+1,这样重新排列而得出的最终结果应该是[1,2,3,4,3,2,7,8],在下标4和下标5的地方元素缺失,此时会被重复的元素2和3随机填充
思路
步骤一: 遍历数组,定义当前下标为i,若当前值与下标不匹配则进行交换,[4,3,2,7,8,2,3,1]这个数组,首先应该交换4和7(下标为nums[i]-1),因此我们可以写出进行交换的条件if(nums[i]!=nums[nums[i]-1])
步骤二: 可以看到在交换后[4,3,2,7,8,2,3,1]这个数组变为[7,3,2,4,8,2,3,1],是不是发现下标0的位置还需要继续交换?,故我们应该把步骤1的if条件更改为循环条件while
步骤三: 经过我们的操作数组已经被变为原地哈希排序后的数组了,接下来只要再遍历一遍数组,找出值!=下标+1的情况,返回结果即可
伪代码
for(num: nums){while(值不对位){交换位置}
}
res=[]
for(num: nums){if(值不对位){res.append(num) }
}
return res答案
def findDisappearedNumbers(self, nums):n = len(nums)if n <= 1:return []for i in range(n):while nums[i] != nums[nums[i] - 1]:nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]res = []for i in range(n):if nums[i] != i + 1:res.append(i+1)return res
注意到我上次说的,在交换数字时,如果后者用到了前者会导致前者的值被预先覆盖,交换失败哦,写成 nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]才是正确的
缺失的第一个正数
做到这里,想必羊羊已经是一位老司机了,这是一道困难题,但我相信难不倒你
题目链接
题目大意: 对于一个正正数序列它从1开始一直到无限大,我们的目标就是找出当前数组中缺失的第一个正整数,题目中说,时间复杂度为O(n),说明只能遍历一次,常数级别的额外空间,说明不能使用字典和集合,所以原地哈希是我们唯一的出路了
难点
- 该题的难点在于交换条件,如果我们按照上一题的交换条件进行交换,由于数组中的值不一定在[1,n]中,很有可能造成数组下标越界的情况,因此需要增加判断,在不越界的情况下,才能进行交换
- 结果的返回,与上题不同,这题只需要返回第一个正数,所以我们遇到值不对位的情况,直接返回即可
- 再来考虑这样一个情况,如果数组为[1,2,3],意思是数组原本就满足于原地哈希规则了,此时我们是不是应该返回4呢,所以如果第二个循环语句检查过程中没有返回结果,我们在最后返回n+1即可
代码
这里直接给出代码了哦
分割线--------------------------------------------------------------------------------------------------------------
def firstMissingPositive(self, nums):n = len(nums)for i in range(n):while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] for i in range(n):if nums[i] != i + 1:return i + 1return n + 1
ps: range(n)函数在python中用于生成0到n-1的序列,常用于循环语句中
例如:
- range(5)生成的序列是0,1,2,3,4
- range(1,5)生成的序列是1,2,3,4
- range(1,5,2)生成的序列是1,3,这是因为2指定的是步长,而range在三个参数时,前两个参数代表的是一个左闭右开的区间[1,5)