Give you an unordered integer array nums. Please find the smallest positive integer that does not appear in it
https://leetcode-cn.com/problems/first-missing-positive/
Advanced: can you implement a solution with a time complexity of O(n) and only use constant level additional space?
Example 1:
Input: num = [1,2,0]
Output: 3
Example 2:
Input: num = [3,4, - 1,1]
Output: 2
Example 3:
Input: num = [7,8,9,11,12]
Output: 1
Tips:
0 <= nums.length <= 300
-231 <= nums[i] <= 231 - 1
Java solution
Idea:
- Find the minimum value that does not appear + not sorted – > sort the data in order
- Create a new corresponding array, store the corresponding data in the subscript position, and store the number of index occurrences
- A value of 0 indicates that the data does not appear, throws, and all appear, indicating the length value
- nums length is used for storage (I don't know whether it meets the advanced requirements, check the official solution below)
package sj.shimmer.algorithm.ten_3; /** * Created by SJ on 2021/2/17. */ class D24 { public static void main(String[] args) { System.out.println(firstMissingPositive(new int[]{1,2,0})); System.out.println(firstMissingPositive(new int[]{3,4,-1,1})); System.out.println(firstMissingPositive(new int[]{7,8,9,11,12})); System.out.println(firstMissingPositive(new int[]{1})); } public static int firstMissingPositive(int[] nums) { if (nums == null||nums.length==0) { return 1; } int[] n = new int[nums.length]; for (int i = 0; i < nums.length; i++) { int num = nums[i]-1;//-1 indicates that the position is moved forward by one bit, and 0 is not a positive number if (num>nums.length-1||num<0) { continue; } n[num] = ++n[num]; } for (int i = 0; i < n.length; i++) { if (n[i]==0) { return i+1; } } return n.length+1; } }
Official solution
The angle algorithm is OK, but the efficiency is not particularly good...
-
Hashtable
The original text can be linked here to express my understanding
-
Set all negative numbers to length + 1 (out of range) and change all data to positive numbers
-
Mark all data within the range (add the subscript value minus one to the value of the data, and there is no need to add it repeatedly)
-
When traversing the data, negative numbers are found, indicating that the next data has experienced marking
-
In comparison, the memory is generally reduced, but it is still constant. Two loops can be optimized into one. I have considered processing on the same array before, but I haven't found a suitable marking method. The official solution is NICE
class Solution { public int firstMissingPositive(int[] nums) { int n = nums.length; for (int i = 0; i < n; ++i) { if (nums[i] <= 0) { nums[i] = n + 1; } } for (int i = 0; i < n; ++i) { int num = Math.abs(nums[i]); if (num <= n) { nums[num - 1] = -Math.abs(nums[num - 1]); } } for (int i = 0; i < n; ++i) { if (nums[i] > 0) { return i + 1; } } return n + 1; } }
- Time complexity: O(N)
- Space complexity: O(1)
-
-
substitution
This should be an idea I thought of but didn't do (mainly to complete a cycle) and put the data back in place
[3, 4, - 1, 1] restored to: [1, - 1, 3, 4]
The official solution is to exchange one correct data per cycle
class Solution { public int firstMissingPositive(int[] nums) { int n = nums.length; for (int i = 0; i < n; ++i) { while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { int temp = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i] = temp; } } for (int i = 0; i < n; ++i) { if (nums[i] != i + 1) { return i + 1; } } return n + 1; } }
- Time complexity: O(N)
- Space complexity: O(1)