The question, https://leetcode.com/problems/first-missing-positive/, asks:

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:

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

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

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

Constraints:

1 <= nums.length <= 5 * 10**5
-2**31 <= nums[i] <= 2**31 - 1

Thus my code satisfies this:

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        nums=sorted(list(filter(lambda x: x>=0, nums)))
        nums= list(dict.fromkeys(nums))
        if 1 not in nums: return 1
        x=nums[0]
        for num in nums:
            if nums.index(num) != 0:
                dif = num - x
                if dif!=1:
                    return x   1
                x=num
        return num 1
                
        

Glad for anyone to offer help.

CodePudding user response：

As the comments described, sorted() doesn't take linear time. sorted() also creates a new list, so your solution also violates the O(1) memory constraint.

Here's a linear-time, constant-space solution. The problem asks for two things (for simplicity, let n = len(nums)):

1. a data structure that can in O(1) time, determine whether a positive integer in the interval [1, n] is in nums. (We have n numbers to check, and the runtime of our algorithm has to be linear.) For this problem, our strategy is to create a table such that for every integer i between 1 and n, if i is in nums, then nums[i - 1] = i. (The answer has to be positive, and the answer can't be greater than n 1 -- the only way for the answer to be n 1 is if nums contains every integer in the interval [1, n]).
2. a procedure to generate the data structure in-place to meet the memory constraint.

Here's a solution that does this.

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # Match elements to their indicies.
        for index, num in enumerate(nums):
            num_to_place = num
            while num_to_place > 0 and num_to_place <= len(nums) and num_to_place != nums[num_to_place - 1]:
                next_num_to_place = nums[num_to_place - 1]
                nums[num_to_place - 1] = num_to_place
                num_to_place = next_num_to_place
        
        # Find smallest number that doesn't exist in the array.
        for i in range(len(nums)):
            if nums[i] != i   1:
                return i   1
        
        return len(nums)   1

Both for loops takes linear time. The reasoning for the second is obvious, but the time analysis of the first is a bit more subtle:

Notice that the while loop contains this condition: num_to_place != nums[num_to_place - 1]. For each iteration of this while loop, the number of values that meet this condition decreases by 1. So, this while loop can only execute at most n times across all iterations, meaning the first for loop takes O(n) time.

CodePudding user response：

I think, that doesn't seem O(n) because of the index inside the loop, thus checking directly without retrieving the index will have an O(n) complexity like this...

lst = [1,2,0]

flag = 0

if 1 not in lst:
    print(1)
else:
    arr = [_ for _ in lst if _>=0]
    amin, amax = min(arr), max(arr)

    for i in range(amin 1, amax):
        if i not in arr:
            flag = 1
            val = i
            break

    print(val) if flag else print(amax 1)

Output:-

3

The time it took for each of the test cases was :-

[1,2,0]       : 3.4332275390625e-05 seconds
[3,4,-1,1]    : 3.886222839355469e-05 seconds
[7,8,9,11,12] : 0.000102996826171875 seconds

CodePudding user response：

Python set is implemented as a hash table. So you can expect to lookup/insert/delete in O(1) average

# O(n) time and O(n) space
class Solution(object):
    def firstMissingPositive(self, nums):
        nums_set = set(nums)
        result = 1
        while True:
            if result not in nums_set:
                return result
            result  = 1

# O(n) time and O(1) space
class Solution(object):
    def firstMissingPositive(self, nums):
    nums_length = len(nums)
    tmp = 0
    for i, num in enumerate(nums):
        while num <= nums_length and num > 0:
            tmp = nums[num-1]
            nums[num-1] = float('-inf')
            num = tmp
                
    for i in range(nums_length):
        if nums[i] != float('-inf'):
            return i   1
        
    return len(nums)   1