内联与基于函数的交换（第一个缺失正值）

Question

我正在尝试解决这个leetcode问题：First Missing Positive。但是，我在执行交换时遇到了问题。

我参考了解决方案here。

因此，不要使用像这样的辅助函数来执行交换，

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        def swap_elements(index1, index2):
            nums[index1], nums[index2] = nums[index2], nums[index1]

        list_length = len(nums)
      
        for i in range(list_length):
            while 1 <= nums[i] <= list_length and nums[i] != nums[nums[i] - 1]:
                swap_elements(i, nums[i] - 1)

        for i in range(list_length):
            if i + 1 != nums[i]:
                return i + 1
      
        return list_length + 1

我尝试执行这样的内联交换

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

两种方法都使用相同的逻辑，但第二种方法不适用于某些输入。

示例：给定输入 [3,4,-1,1]，第一种方法将像这样改变

nums

[-1, 4, 3, 1] --> [-1, 1, 3, 4] --> [1, -1, 3, 4]

但是第二种方法会导致无限循环

[-1, 4, 3, 1] --> [4, 1, 3, 1] --> [4, 4, 3, 1] --> [4, 1, 3, 1] --> [4,4,3,1]...

提前致谢！

Answer 1

您只需要“存储”索引并将其重新用于交换的第二部分：

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