Location>code7788 >text

[Ninja Algorithm] From library cataloging to array search: Exploring the missing first positive integer | LeetCode 41 Missing first positive integer

Popularity：233 ℃/2025-02-06 23:37:13

From library cataloging to array search: Exploring the missing first positive integer

Algorithms in life

Imagine you are a library administrator who is organizing a row of consecutive numbers of books. These books should be arranged in order starting from No. 1, but some numbered books are gone. Your task is to find out the first missing number. It's like doing a naming call and discovering the first classmate who didn't come to class.

This scene is very common in life. for example:

  • Restaurant waiter checks which table number is the first empty space
  • Parking lot manager looking for the first free parking number
  • The school assigns the first unused student number to freshmen
  • The hospital arranges the first available consultation number for the patient

Problem description

LeetCode Question 41 "The first positive integer missing" is described as follows: I give you an array of unsorted integers nums, please find out the smallest positive integer that does not appear. Please implement a solution with a time complexity of O(n) and only using the additional space at the constant level.

For example:

Input: nums = [3,4,-1,1]
 Output: 2
 Explanation: There are 1, 3, 4 in the array, so the first missing positive integer is 2.

 Input: nums = [7,8,9,11,12]
 Output: 1
 Explanation: There is no 1 in the array, so the first missing positive integer is 1.

The most intuitive solution: traversal after sorting

Just like when sorting out books, first sort all the books in order, and then check from 1 to see which number is the first to be vacant.

Let's use a simple example to understand:

Original array: [3,1,4,-1]
 1. Sort first (consider only positive numbers): [1,3,4]
 2. Start checking from 1:
    - 1 Existence
    - 2 does not exist, find the answer!

Optimization solution: In-place marking

If you think carefully, you will find a key point: if the length of the array is n, then the answer must be within the range of [1, n+1]. Just like a class with 10 students, the first student number that is absent will not exceed 11.

We can use the array itself as a marker board and place each number where it should be (like putting each book in the corresponding numbered position).

Principle of in-place marking

  1. Put each number x in the range [1,n] to the position of index x-1
  2. Iterate again, the first number not in the corresponding position indicates the missing minimum positive integer
    It's like:
  • First put each book on the shelf position corresponding to its number
  • Then start checking from position 1 and find the first empty position

Sample Demo

Use nums = [3,4,-1,1] to illustrate:

1. Start moving elements:
    [3,4,-1,1] Put 3 to index 2
    [3,4,3,1] Put 4 to index 3
    [3,1,3,4] Put 1 to index 0
    [1,3,3,4]

 2. Circle again and check each location:
    Position 0: Expected 1, Actual 1, Correct
    Position 1: Expect 2, Actual 3, Answer 2 found!

Java code implementation

public int firstMissingPositive(int[] nums) {
     int n = ;
    
     // The first time traversal: put each number where it should be
     for (int i = 0; i < n; i++) {
         // The current number is in the valid range and is not in the correct position
         while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
             // Switch to the correct position
             int temp = nums[nums[i] - 1];
             nums[nums[i] - 1] = nums[i];
             nums[i] = temp;
         }
     }
    
     // The second traversal: Find the first number that is not in the correct position
     for (int i = 0; i < n; i++) {
         if (nums[i] != i + 1) {
             return i + 1;
         }
     }
    
     // If all are correct, return n+1
     return n + 1;
 }

Solution comparison

Let's compare these two methods:

After sorting, traversal:

  • Time complexity: O(nlogn)
  • Space complexity: O(1)
  • Advantages: Intuitive thinking, easy to understand
  • Disadvantages: Not meeting the time complexity requirements

Place mark:

  • Time complexity: O(n)
  • Space complexity: O(1)
  • Advantages: Meet all requirements, no extra space required
  • Disadvantages: The implementation is slightly complex and requires careful handling of the boundary situation

Summary of problem solving skills

This question gives us the inspiration:

  1. It is important to think about the value range of data
  2. Sometimes you can use the array itself as a marker array
  3. The correspondence between position and value often brings inspiration
  4. Don't be afraid to modify the original array, sometimes this is the key to improving efficiency

Similar questions include:

  • Duplicate numbers in array
  • Find all the missing numbers in the array
  • Looking for repetitions

summary

Through the problem of missing first positive integer, we learned an important way of thinking: sometimes problems that seem to require extra space can be solved by cleverly using the input array itself. This kind of thinking is not only useful in this question, but also inspiring when dealing with other issues that require marking or counting. Remember, when you encounter the problem of finding missing numbers in a specific range, consider whether you can use the array itself to store information!

Author: Ninja Algorithm
Official account: Ninja Algorithm

Complete question-solving project:/ninjaAlgorithm/LeetCode-Solutions-Hot-100

<Previous Next>