41. 缺失的第一个正数

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

解法一:

把所有正数i放到数组中第i-1个位置上,即理想情况应该是[1,2,3,...],然后从头遍历,找第一个不符合该条件的,就是没出现的最小正数。

难点在于怎么放。对于给定位置i,其值应该为i+1,同理对于给定值nums[i],其位置应该为nums[i]-1

从i=0开始遍历数组,若nums[i] == i+1,符合该条件的不用修改;此外非正数也不用修改;还有位置超出数组长度的也不用修改。

若不满足nums[i] == nums[nums[i]-1],交换这两个数,将i处的数字放到合适位置,使其符合要求(为何用值来确定位置?因为位置是连续的从0~n-1,而值不一定能满足这些位置要求,所以只能根据值来定位)

其余情况直接跳过

此外交换时不能直接用a,b=b,a方式交换,因为下标嵌套了数组,交换过程中已经改变了相应的下标。应该写成函数来处理

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        i = 0
        while i < len(nums):
            if nums[i] == i+1 or nums[i] <= 0 or nums[i]-1 >= len(nums):   #跳过
                i += 1
            elif nums[i] != nums[nums[i]-1]:
                self.swap(nums, i, nums[i] - 1)  # 调用函数交换
            else:
                i += 1
        #第二次遍历
        i = 0
        while i < len(nums) and nums[i] == i+1:
            i += 1
        return i+1

    def swap(self, nums, i, j):  # 交换函数
        nums[i], nums[j] = nums[j], nums[i]

最后更新于