力扣练习之缺失的第一个正数

我爱海鲸 2023-08-04 20:19:35 力扣、高级算法

简介高级、力扣、

原题出处:https://leetcode.cn/leetbook/read/top-interview-questions-hard/xwkftg/

解法一(python):

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        if not nums:
            return 1
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        
        return n + 1

思路:

  1. for i in range(n): 这一行是一个循环,它会遍历数组中的每一个元素。其中,n 是数组的长度。

  2. while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: 这一行是一个条件判断语句。它的意思是,只要当前元素在正确的位置上(即在1到n之间),并且它的正确位置上的元素不等于它自己,那么就继续执行下面的操作。

  3. nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] 这一行是一个交换操作。它的意思是,将当前元素和它的正确位置上的元素进行交换。这样,经过一次或多次这样的交换操作后,数组就会被排序。

总的来说,这段代码的作用就是通过不断地交换元素的位置,使得数组中的每一个元素都在正确的位置上。这就是荷兰国旗问题的解法。

你好:我的2025