This is the 11th day of my participation in the August Wenwen Challenge.More challenges in August

The title

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. 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 warning: 1 <= nums.length <= 5 * 105-231 <= nums[I] <= 231-1 https://leetcode-cn.com/problems/first-missing-positiveCopy the code

The title gives the following supplementary information:

  • Think about how you would solve the problem in non-constant space. Can you apply that logic to the existing space?
  • We don’t care about duplicates or non-positive integers
  • Remember that O(2n) = O(n)

The method signature

 public static int firstMissingPositive(int[] nums) {
 ​
 }
Copy the code

parsing

Order n, we can’t sort it and then find it sequentially, or our algorithm dictates that we have to do it sequentially several times.

Second, we are required to use extra space at the constant level, and we can no longer use hashMaps or similar dictionaries to record, or we can only record with a certain number of variables.

So, what do we do?

In the simplest way, of course, we want to:

  • Read the array once, and you get the information
  • Records the information that has been read

In fact, we know:

  • For a given array, assuming length n, consecutive positive integers starting at 1 are at most n. (1)
  • And the array given in the problem does not have to be the same before and after the method is executed, which means we can make changes to the array.

So let’s do the given array like this:

  • Using the input array, record the results we read.

Why is it okay to do that?

  • The reason is simple:

    • From (1) we can deduce that if we record the numbers in order, then after recording, we can read the record to know that the first missing positive integer is either (0,n) or n+1(the array contains all the numbers).
    • Note that we don’t care about values that are negative, and in fact we don’t care about values greater than n (because at the end of the day we just need to know which number doesn’t appear in the interval (1,n)).

Then we record the read result according to the following ideas:

  • We read back to front, placing the numbers in the corresponding boxes:

Remember that the read number is a, the array is arr, and the corresponding index of A is I. We swap arr[a] and arr[I], and stop at this point, and continue to check the position of I next time to avoid omission

If it’s outside the range of the array, we give it a special value, which means we don’t care, which reduces the cost of our next judgment;

If we read the entire number and still have this special value, it means that the number corresponding to the index is not in the array.

  • In addition, in order to prevent the endless loop caused by the same number, we need to compare the same number when swapping.

code

public static int firstMissingPositive(int[] nums) { System.out.println(""); for (int i = 0; i < nums.length; i++) { if(nums[i]<=0) continue; if(nums[i]-1 >= nums.length){ nums[i] = 0; continue; } if(nums[i]-1 == i) continue; int tmp = nums[i] == nums[nums[i]-1]? 0:nums[nums[i]-1]; nums[nums[i]-1] = nums[i]; nums[i] = tmp; i--; } int idx; for (idx = 0; idx < nums.length; idx++) { if(nums[idx]-1! =idx) return idx+1; } return idx+1; }Copy the code

\