假设对于大小为n(n>0)的数组,这n个数可以分为以下几种情况:
- n个数都小于等于0
- n个数都大于n
- 存在一个或多个位于[1,n]的数
对于情况1,要查找的第一个缺失的正数就是1;对于情况2,要查找的第一个缺失的正数也是1;问题是对于情况3应该怎么考虑
假设这些位于[1,n]的数i,在数组中的位置为i-1,而小于等于0的数,以及大于n的数,在数组剩余位置:
- 如果数组所有的数都在[1,n],那么每个元素都在其值减1的位置,此时要找的第一个缺失的整数就是n+1
- 否则,数组中,必然存在一个位置idx,其元素值不等于idx+1,而范围[1,n]就是正数序列最开始的n个数,因此,从左往右查找第一个下标加1不等于值的位置,那么要找的第一个缺失的正数就是该位置的下标加1
剩下的就是将范围在[1,n]的元素放置到正确的位置了。
使数组大小为n,刚好可以放下前n个正数,由于0不是正数,那么将数组下标i的槽存放正数i+1。经过这样的处理后,第一个不满足上述关系的槽应该存放的那个正数,就是第一个缺失的正数