This is the 30th day of my participation in the August Text Challenge.More challenges in August

To participate in more text 30 days, is a thing to insist on down, tomorrow the last day, continue to refueling. Today we will continue leetcode problem 41, difficulty level is difficult.

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

 

1 <= nums.length <= 5 * 105-231 <= nums[I] <= 231-1

Train of thought

Read the title description and restrictions, really stumped. Time complexity O(n) is not difficult, just using constant level extra space is not difficult, but to satisfy both, that’s the hard part. Read the solution, know a new idea, and after reading the idea, even without looking at the follow-up specific solution, also quite let a person suddenly enlightened. In a word: Use the array itself nums to store something. And someone even came up with a name, which I think is appropriate, which is in-situ hashing. First, find the smallest positive integer that doesn’t exist, so if the array is len, the answer can only exist in the range [1, Len +1], because if the array happens to be 1 len, then the answer is len+1, otherwise, it must be the smallest missing integer in 1 len. If the value is in [1, len], swap it with nums[I]-1, so that the first value is 1 and the second value is 2, all the way down. If the NTH value is not n, then n is the answer. The idea is to put all the numbers in the correct position, and then iterate again to find the first number that is not in the correct position. If the nums[I]-1 subscript is already nums[I], it is not necessary to swap. The steps of the exchange may seem abstract, but I have drawn a diagram that identifies the method of exchange at each step:

Finally, iterate through the array again. The first one is 1, the second one is not 2, so the answer is 2.

Java version code

class Solution { public int firstMissingPositive(int[] nums) { int len = nums.length; for (int i = 0; i < len; i++) { while (nums[i] >= 1 && nums[i] <= len && nums[i] ! [nums = nums [I] 1]) {/ / exchange nums [I] and nums [nums [I] 1] int k = nums [I] 1. nums[i] += nums[k]; nums[k] = nums[i] - nums[k]; nums[i] -= nums[k]; } } for (int i = 0; i < len; i++) { if (nums[i] ! = i+1) { return i+1; } } return len + 1; }}Copy the code