This is the 21st day of my participation in the August Text Challenge.More challenges in August

The first positive integer missing

Given an unsorted integer array nums, find the smallest positive integer that does not appear in it.

You implement a solution with O(n) time complexity and use only constant level extra space.

Tip:

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

It is not too difficult to work out the problem without regard to the additional conditions.

If you want the time complexity to be O(n), you can store it as a Hash table and search for the missing value from 1, but the space complexity will reach O(n), which does not meet the requirements of O(1).

If you want the space complexity to be O(1), you can start from 1 and iterate through the array until you find the missing value, but then the time complexity reaches O(n^2), which does not meet the requirements of O(n).

For this problem, I refer to the algorithm provided by LeetCode and use the idea of recovering arrays:

Move each integer nums[I] in the range 1 to n to nums[I]-1, the nums[I] element of the array:

As shown, I =0, nums[0]=4. Swap nums[0] with nums[3], making 4 the fourth element of the array (nums[i-1]).

Note that the swapped 2 is not where it should be either (it should be 1 at I =0), so repeat the swap:

Continue to the next digit, if the next digit is in the correct position, skip; If it is not in the range of 1 to n (out of the range of the array), skip is also performed (this position may show the answer we want, but there is a possibility of the corresponding number, so skip first, and confirm later).

After traversing and swapping, we get a regular array:

Iterate over the array. If nums[I]! = I +1, then the smallest missing positive integer is I +1, as nums[4] == -1! = 5, the smallest positive integer missing is identified as 5. If the entire array is continuous from 1, then n+1 is the least missing positive integer.

The time complexity is O(n) and space complexity is O(1), which meet the requirements of the question.

For arrays with no duplicate digits, the above steps are sufficient, but if duplicate digits are present, the two digits are always interchangeable, so for two identical digits in the range 1 to n, an extra count is needed to break the loop.

The code implementation is as follows:

func firstMissingPositive(nums []int) int {
    n := len(nums)
    for i := 0; i < n; i++ {
        for 0 < nums[i] && nums[i] <= n && nums[nums[i]- 1] != nums[i] {
            nums[nums[i]- 1], nums[i] = nums[i], nums[nums[i]- 1]}}for i := 0; i < n; i++ {
        ifnums[i] ! = i +1 {
            return i + 1}}return n + 1
}
Copy the code

Submission Results: