LeetCode 学习：缺失的第一个正数

https://leetcode-cn.com/problems/first-missing-positive/submissions/

题目

错误版本

自己的思路是找出其中的最大正数、最小正数，划分为3个区间，然后根据缺失正数是在左边、区间内、右边的情况进行分别判断。判断缺失数字是在左边、右边的条件是，所有正数的个数 与（最大正数-最小整数）的大小关系，但是，这隐含了正数不重复出现的条件，所以这个方法有问题。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        miss_num=1
        min_num = nums[0]
        max_num=nums[0]
        positive_len=0

        # 找出最小正整数,最大正整数
        for i in nums:
            if i>0:
                positive_len +=1
            if 0<i<min_num:
                min_num = i
            if i>max_num:
                max_num = i
        
        # 缺失值在左边
        if min_num > 1:
            for i in range(1,min_num):
                if i < min_num:
                    return i

        # 缺失值在右边
        if max_num-min_num+1 == positive_len:
            return max_num+1

        # 缺失值在范围内
        for i in range(min_num+1,max_num):
            count_s = 0
            for j in nums:
                if i>=j:
                    break
                else:
                    count_s +=1
            if count_s == positive_len-1:
                return i

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        miss_num=1
        # 判断有没有数
        if nums ==[]:
            return 1
        min_num = 0
        max_num=0
        positive_len=0

        # 找出是否有正整数
        for i in nums:
            if i>0:
                min_num=i
                max_num=i
                break
        if min_num==0: #没有正整数
            return 1

        # 找出最小正整数,最大正整数,正整数的个数
        for i in nums:
            if i>0:
                positive_len +=1
                if i<min_num:
                    min_num = i
                if i>max_num:
                    max_num = i
        
        # 缺失值在左边
        if min_num > 1:
            for i in range(1,min_num):
                if i < min_num:
                    return i

        # 缺失值在右边
        if max_num-min_num+1 == positive_len:
            return max_num+1

        if min_num == max_num:
            return min_num+1

        # 缺失值在范围内
        for i in range(min_num+1,max_num):
            count_s = 0
            for j in nums:
                if i<j:
                    count_s +=1
            if count_s == positive_len-1:
                break
        return i

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        miss_num=1
        # 判断有没有数
        if nums ==[]:
            return 1
        min_num = 0
        max_num=0
        positive_len=0

        # 找出是否有正整数
        for i in nums:
            if i>0:
                min_num=i
                max_num=i
                break
        if min_num==0: #没有正整数
            return 1

        # 找出最小正整数,最大正整数,正整数的个数
        for i in nums:
            if i>0:
                positive_len +=1
                if i<min_num:
                    min_num = i
                if i>max_num:
                    max_num = i
        
        # 缺失值在左边
        if min_num > 1:
            for i in range(1,min_num):
                if i < min_num:
                    return i

        # 缺失值在右边
        if min_num == max_num:
            return min_num+1

        # 缺失值在范围内
        for i in range(min_num+1,max_num):
            count_s = 0
            for j in nums:
                if i<j:
                    count_s +=1
            if count_s == positive_len-1:
                break
        return i

查看官方答案思路

仍然利用了索引作为哈希表，跟之前做的题关联起来了。整体来说需要进行的步骤有：

• 检查是否有1
• 检查是否只有1
• 用1替换掉所有的负数和零
• 存在的正数作为索引，其对应数值变为负号
• 找出数组中的第一个正数，其对应索引就是缺失的。
• 如果全为负数，则缺失的是len（nums）+1.

错误版本2

然而，明白了整体的思路，没有理解到细节，还是犯错了。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 检查是否有1
        if 1 not in nums:
            return 1

        # 检查是否只有1
        if nums == [1]:
            return 2

        # 利用1替换所有的负数和零
        for index, data in enumerate(nums):
            if data <= 0:
                nums[index] = 1

        # 利用索引作为哈希表，检查包含哪些正整数
        for index, data in enumerate(nums):
            if  data > 0:
                nums[data-1]=-1
        # 找出第一个保存正整数的
        for index, data in enumerate(nums):
            if data >0:
                return index+1

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 检查是否有1
        if 1 not in nums:
            return 1

        # 检查是否只有1
        if nums == [1]:
            return 2

        # 利用1替换所有的负数和零
        for index, data in enumerate(nums):
            if data <= 0:
                nums[index] = 1
        #return nums
        # 利用索引作为哈希表，检查包含哪些正整数
        for index, data in enumerate(nums):
            if  len(nums)+1>data > 0 :
                nums[data-1]=-1
        return nums
        # 找出第一个保存正整数的
        for index in range(1,len(nums)):
            if nums[index] > 0:
                return index+1
        
        return len(nums)+1

最后一位应该最后检查，不然容易改变数值。
所以答案中，第一次遍历，只改变了符号，而没有改变数值。

没有兼顾好标记符号与数值本身之间的关系。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 检查是否有1
        if 1 not in nums:
            return 1

        # 检查是否只有1
        if nums == [1]:
            return 2

        # 利用1替换所有的负数和零
        for index, data in enumerate(nums):
            if data <= 0:
                nums[index] = 1
        #return nums
        # 利用索引作为哈希表，检查包含哪些正整数
        for  i in nums:
            if 0<abs(i)<len(nums)+1:
                nums[abs(i)-1] = -nums[abs(i)-1]

        # 找出第一个保存正整数的
        for i in range(1,len(nums)):
            if nums[i] > 0:
                return i+1
        
        return len(nums)+1

正确版本

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 检查是否有1
        if 1 not in nums:
            return 1

        # 检查是否只有1
        if nums == [1]:
            return 2

        # 利用1替换所有的负数和零
        for index, data in enumerate(nums):
            if data <= 0:
                nums[index] = 1
        #return nums
        # 利用索引作为哈希表，检查包含哪些正整数
        for  i in nums:
            if 0<abs(i)<len(nums)+1 and nums[abs(i)-1]>0:
                nums[abs(i)-1] = -nums[abs(i)-1]
        #return nums
        # 找出第一个保存正整数的
        for i in range(1,len(nums)):
            if nums[i] > 0:
                return i+1
        
        return len(nums)+1