LeetCode——缺失的第一个正数(First Missing Positive)(自己写的代码）

青旅半醒 2022-05-14 09:18 90阅读 0赞

**题目**：

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

**示例 1:**

输入: [1,2,0]
    输出: 3

**示例 2:**

输入: [3,4,-1,1]
    输出: 2

**示例 3:**

输入: [7,8,9,11,12]
    输出: 1

**思路**:刚开始想了很久没有想出来，后面简单看了下别人的博客，发现几乎全部都是用桶排序的思想解决的，这里简单说下桶排序，就是排序一串连续的数组，然后刚开始初始化跟数组一样的桶组合，遍历数组，然后把数字的值当做索引，放入相应的桶中。本题可以用这种思想，当然需要进行一定的修改。首先确定最小的正整数是1，也就是说有1则另外讨论，没有1则直接返回1.

当有1的时候，则要分两种情况，一种是从头到尾都是连续的，则需要返回最大值+1，另一种则是从头到尾不连续，中间有缺失值，这就要返回那个缺失值。

最后说一点，桶的大小是根据数组的大小设定的，也就是说index=0要么不存放，要么存放大于桶内其他值的数，为什么呢？这里我解释一下，桶组合最理想存放的情况是：如果大小为5，则桶为\[5,1,2,3,4\],但是如果这样呢？\[-1,1,7,3,4\],7明显是进行7/5>0的，所以对于这种数，我们不需要放入桶中，或者后期直接排除。**因为有1在，所以我们的缺失值会在(1,桶大小\]之间**。

**代码**：

class Solution:
        def firstMissingPositive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            #这里是对size=0或者1的情况处理
            if len(nums) == 0:
                return 1
            elif len(nums) == 1 and nums[0] !=1:
                return 1
            elif len(nums) == 1 and nums[0] ==1:
                return 2
            buckets = [-1 for num in nums]
            bucketSize = len(buckets)
            for num in nums:
                if num > 0:
                    #放进一个桶里的数一定要最小
                    if buckets[ int(num % (bucketSize)) ] == -1:
                        buckets[ int(num % (bucketSize ))] = num
                    elif buckets[ int(num % (bucketSize)) ] > num:
                        buckets[int(num % (bucketSize))] = num
            #如果在1的位置上没有1，则直接返回1
            if buckets[1] != 1:
                return 1
    
            for index, bucket in enumerate(buckets):
                if index == 1 and bucket == -1:#index=1，那个位置没有,则直接返回1
                    return 1
                elif index !=0 and bucket != index:#如果桶内值不等于索引，则说明进行%操作时，商不为0
                    return index
                elif index!=0 and bucket == -1:#这个桶没有放入值，则说明这是一个缺失值
                    return buckets[index -1] +1
            #到这里说明只剩下index=0,这里的值一般都是最大的数
            if buckets[0] == -1:#第0个桶等于0，则说明数组是这样【1，2，3，4】连续的，所以需要返回5
                return buckets[bucketSize - 1] + 1
            else:#否则就是有值
                if buckets[0] - buckets[bucketSize -1] > 1:#如果最大的数与末尾数相差大于1，则返回末尾数+1,情况如[1000,1]
                    return buckets[bucketSize - 1] + 1
                return buckets[0] + 1#否则返回最大数+1,情况如[3,1,2]
    if __name__ =="__main__":
        res = Solution()
        print(res.firstMissingPositive([3, 1 ] ))
        pass