原题出处: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
思路:
-
for i in range(n):
这一行是一个循环,它会遍历数组中的每一个元素。其中,n
是数组的长度。 -
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
这一行是一个条件判断语句。它的意思是,只要当前元素在正确的位置上(即在1到n之间),并且它的正确位置上的元素不等于它自己,那么就继续执行下面的操作。 -
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
这一行是一个交换操作。它的意思是,将当前元素和它的正确位置上的元素进行交换。这样,经过一次或多次这样的交换操作后,数组就会被排序。
总的来说,这段代码的作用就是通过不断地交换元素的位置,使得数组中的每一个元素都在正确的位置上。这就是荷兰国旗问题的解法。