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

https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/

The angle algorithm is OK, but the efficiency is not particularly good...

1. Hashtable

   The original text can be linked here to express my understanding

   1. Set all negative numbers to length + 1 (out of range) and change all data to positive numbers

   2. 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)

   3. When traversing the data, negative numbers are found, indicating that the next data has experienced marking

   4. 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)

2. 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)