Given an unsorted integer array nums, find the smallest positive integer that does not appear in it. Implement a solution with O(n) time complexity and use only constant level extra space.

Example 1:

Input: nums = [1,2,0] output: 3Copy the code

Example 2:

Nums = [3,4,-1,1Copy the code

Example 3:

Input: nums = [7,8,9,11,12] output: 1Copy the code

Tip:

  • 1 <= nums.length <= 5 *
    1 0 5 10^5
  • –
    2 31 2^{31}      <= nums[i] <=
    2 31 2^{31}      – 1

To find the first missing positive number correctly, the first time I didn’t think of the hash table, the problem is more difficult to solve. The first scheme that comes to mind is to record the effective region and dynamically submit the effective region while traversing NUMS. For example, initialize the effective region ranges as [[1, Infinity]] and take NUMs [3, 4, -1, 1] as an example:

  • The first number is 3 and the ranges split into [[1, 3], [4, Inifinity]]
  • The second number is 4, the ranges are adjusted to [[1, 3], [5, Inifinity]]
  • .

After going through all the data, ranges are finally [[2, 3], [5, Inifinity]], then the minimum value of the first term of ranges array is the “missing first positive number” as we require.

/** * @param {number[]} nums * @return {number} */ var firstMissingPositive = function(nums) { Let ranges = [[1, Infinity]] for (let vi = 0; vi < nums.length; Vi ++) {const value = nums[vi] for (let rgej = 0; rgej < ranges.length; Rgej ++) {const min = ranges[rgej][0], Max = ranges[rgej][1] // If (min < value && value < Max) {ranges. Splice (rgej, 1, [min, value - 1], [value + 1, Max]) // Rgej ++} else {if (min === value) {ranges[rgej] = [min + 1, Max]} else if (Max === value) {ranges[rgej] = [min, max-1]} If (ranges[rgej][0] > ranges[rgej][1]) {ranges. Splice (rgej, 1) rgej--}}}} return ranges[0][0]};Copy the code

This method requires dynamic adjustment of ranges, and there are many judgments. For example, if the current value is within the range of (min, Max), the range of (min, Max) needs to be split into [min, value-1] and [value + 1, Max]. In an ideal case, the length of ranges is always 1, for example, NUMs is [1, 2, 3, 4], and finally ranges become [[5, Infinity]]. The time complexity is O(N), and the space complexity is O(1). In the worst case, the length of the ranges eventually changes to nums.length + 1, for example, nums is [3, 10, 5, 8], and eventually the ranges become [[1, 2], [4, 4], [6, 7], [9, 9], [11, Infinity]]. The time complexity is O(N2N^2N2) and the space complexity is O(N). If the array length is n, the number from 1 to n contains n positive numbers 1,2,3… N, as long as the array is duplicated or not in the range 1 to n, then the missing first positive number must be in the range [1,n]. If nums is exactly [1,2… n], then we know that the required number is n + 1. If a hash table of length N is defined with consecutive numbers from 1 to N, the value at nums[i-1] can be marked with a special number if the number at position I in NUMS is in the range from 1 to n. Then the first unmarked index will be the required number. For example, if nums is [3, 4, -1, 1], the hash table after the identifier is [-1, 0, -1, -1], and -1 is a special identifier, then the first unrepresented index is 1 and the required digit is 2(the index starts from 0). However, the space complexity is required to be O(1), so we can not create a hash table alone, but can directly modify the label on the original array with the idea of hash table. If we use negative numbers to indicate that the current position is occupied, we need to first convert the original negative number to any positive number outside the range of [1, n], such as n + 1. Again take [3, 4, -1, 1] as an example:

  • First, change -1 to 5, change the array to [3, 4, 5, 1], and iterate over the number array.
  • The first value is 3, making the position of index 2(index 0) negative and the array [3, 4, -5, 1].
  • The second value is 4, making the index 3 position negative and the array [3, 4, -5, -1].
  • The third value is -5. Take the absolute value and find the original value 5, not in the range [1, n].
  • The fourth value is -1, the original value is 1, and the array becomes [-3, 4, -5, -1].
  • Iterate through the array again to find the first positive index I, so I + 1 is the desired number. If there are no positive numbers, then the required value is n + 1.
/** * @param {number[]} nums * @return {number} */ var firstMissingPositive = function(nums) {// firstMissingPositive = function(nums) { Const len = nums.length const len = nums.length const len = nums.length const len = nums.length const len = nums.length const len = nums.length For (let I = 0; i < len; I++) {if (nums [I] < = 0) {nums [I] = len + 1}} / / if the value in the range of [1, len]. For (let I = 0; for (let I = 0; i < len; i++) { if (0 < Math.abs(nums[i]) && Math.abs(nums[i]) <= len) { const tagIndex = Math.abs(nums[i]) - 1 nums[tagIndex] = -math.abs (nums[tagIndex])}} // if (let I = 0; i < len; i++) { if (nums[i] > 0) { return i + 1 } } return len + 1 };Copy the code

The time complexity of this method is O(N) and the space complexity is O(1). In a similar way, we can also consider permutation to place the number in the correct position for [1, n], such as placing the number x(in the range [1, n]) in the corresponding index position: nums[x-1] = x. So the first index that doesn’t match the number is the number. For example, numS array [3, 4, -1, 1], traversal case:

  • Nums [2] = 3; nums[0] = -1; nums[0] = -1
  • Index 0, value -1, out of range [1 n], traversed down.
  • Nums [3] = 4, nums[1] = 1.
  • Index 1, nums[0] = 1, nums[1] = -1, nums[1] = -1, -1 is not in the range [1,n], traverses.
  • .

The resulting array is [1, -1, 3, 4]. The second position does not match the index, so 2 is the desired number.

/** * @param {number[]} nums * @return {number} */ var firstMissingPositive = function(nums) { Const len = nums.length for (let I = 0; let I = 0) const len = nums.length for (let I = 0; i < len; I++) {// [3,4,-1,1], nums[3-1], nums[4-1], -1 skip,1, nums[1-1] If nums[I] is not in [1, len] or nums[I] = I + 1 Will terminate the current substitution while (1 <= nums[I] && nums[I] <= len && nums[NUMs [I] -1]! == nums[i]) { const tempVal = nums[nums[i] - 1] nums[nums[i] - 1] = nums[i] nums[i] = tempVal } } for (let i = 0; i < len; i++) { if (nums[i] ! == i + 1) { return i + 1 } } return len + 1 };Copy the code

The substitution loop continues until the current number is not in the range of [1, n]. If every index position in the array corresponds to the value, then the value is n + 1. Although a while loop is used in a function, the loop stores the value to the correct location ahead of time, so subsequent traversals of the while are skipped. The final time is O(N), and the space is O(1).