Skip to content

Latest commit

 

History

History
126 lines (95 loc) · 3.54 KB

0041._First_Missing_Positive.md

File metadata and controls

126 lines (95 loc) · 3.54 KB

41. First Missing Positive

难度: Hard

刷题内容

原题连接

内容描述

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3
Example 2:

Input: [3,4,-1,1]
Output: 2
Example 3:

Input: [7,8,9,11,12]
Output: 1
Note:

Your algorithm should run in O(n) time and uses constant extra space.

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

题目要求O(n)时间和O(1)空间，所以我们知道先排序再循环找是不行的

因此我们可以这样，第一轮循环，找1(因为1是最小的正整数)，如果1在，立马原地开始继续找2，以此类推，一轮循环结束后，我们记录下当前正在找的值i， 并开始第二轮循环，但是这次从i开始找了，然后以此类推，直到有一次循环我们要找的值没有变过，则代表它没出现过，返回它即可

可以看一个例子

[3,4,-1,1]

第一轮循环：[1,1,1,2]
第二轮循环：[2,2,2,2]

然后我们发现第二轮循环2没有变过了，所以2就是我们要的结果

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        old_missing, missing = 0, 1
        while old_missing != missing:
            old_missing = missing
            for i in range(len(nums)):
                if nums[i] == missing:
                    missing += 1
        return missing

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******

如果不限制空间的话，我们用一个dict就可以解决, 时间是O(N)

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 1
        lookup = {}
        for i in nums:
            lookup[i] = 1
        for i in range(1, len(nums)+2):
            if i not in lookup:
                return i

思路 3 - 时间复杂度: O(N)- 空间复杂度: O(1)******

参考[email protected] 先把所有的数字都放到该放的地方去，最后来一个for循环看哪个位置上没有对应的数字，就返回那个数字

  • 1st sweep through the array and swap the number to its appropriate index (i.e 3 should go to index 3 - 1 = 2)
  • 2nd sweep check if the number is at the appropriate index (i.e at index 2 nums[i] should be 3)
    • if not return i + 1
  • Edge case when all the numbers are in the appropriate indices then return n + 1
class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) == 0:
            return 1

        for i in range(len(nums)):
            # swap nums[i] to i - 1 then use nums[i - 1] as new target to swap
            while nums[i] > 0 and nums[i] <= len(nums) and nums[nums[i]-1] != nums[i]:
                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
        return len(nums) + 1