This is the 28th day of my participation in the August Challenge

1. Title Description

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

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

Tip: Your algorithm should have O(n) time complexity and can only use constant levels of extra space.

Source: LeetCode

2. How to solve the problem

  1. The problem requires O(n) complexity, so you can’t do sorting first;
  2. Because it is A positive integer array, it should be sorted like the [1,2,3,4… n] array A.
  3. If any element in the “adjusted” array B does not match A, that element is the smallest missing positive integer.
  4. This “adjustment” is done by placing 1 in the first position of the array whenever possible, 2 in the second position of the array, and so on.
  5. Finally, traverse group B from left to right to find the first index! = the value of -1, which is the answer.

Reference code

Class Solution {public int firstMissingPositive (int [] nums) {/ / abnormal input inspection & filter the if (null = = nums | | 0 = = nums. Length) { return 1; } int i = 0; while (i < nums.length) { int val = nums[i]; If (val < = 0 | | val = = I + 1 | | val > nums. Length) {/ / do not accord with the question of outliers, skip does not handle i++; continue; } // the index 0 should be 1, so the index val-1 should be val int index = val-1; Int tmpVal = nums[index]; Val nums[index] = val; If (val == tmpVal) {nums[i++] = 0; } else {nums[I] = tmpVal; }} // Walk left to right through the "adjusted" array to find the first index! For (I = 0; i < nums.length; i++) { if (nums[i] ! = i+1) { return i+1; } } return nums.length + 1; }}Copy the code