Bài 41 Leetcode: First Missing Positive

Đề bài:

Cho một mảng số nguyên nums không được sắp xếp, hãy trả về số nguyên dương nhỏ nhất bị thiếu. Bạn phải thực hiện một thuật toán chạy trong thời gian O(n) và sử dụng không gian phụ O(1).

Ví dụ 1:

Input: nums = [1,2,0]
Output: 3
Giải thích: Các số trong khoảng [1,2] đều có trong mảng.

Ví dụ 2:

Input: nums = [3,4,-1,1]
Output: 2
Giải thích: Số 1 có trong mảng, nhưng số 2 bị thiếu

Ví dụ 3:

Input: nums = [7,8,9,11,12]
Output: 1
Giải thích: Số nguyên dương nhỏ nhất 1 bị thiếu.

Ràng buộc:

• 1 <= độ dài của nums <= 10^5
• -2^31 <= nums[i] <= 2^31 – 1

Giải thích thuật toán bằng C ++

class Solution {
 public:
  int firstMissingPositive(vector<int>& nums) {
    const int n = nums.size();

    // Correct slot:
    // nums[i] = i + 1
    // nums[i] - 1 = i
    // nums[nums[i] - 1] = nums[i]
    for (int i = 0; i < n; ++i)
      while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])
        swap(nums[i], nums[nums[i] - 1]);

    for (int i = 0; i < n; ++i)
      if (nums[i] != i + 1)
        return i + 1;

    return n + 1;
  }
};

Đoạn mã trên là một đoạn mã C++ để tìm số nguyên dương nhỏ nhất bị thiếu trong một mảng số nguyên. Dưới đây là giải thích về thuật toán trong đoạn mã:

1. Hàm `firstMissingPositive` nhận một vector `nums` là mảng các số nguyên và trả về số nguyên dương nhỏ nhất bị thiếu.

2. Đầu tiên, ta khai báo một hằng số `n` để lưu độ dài của mảng `nums`.

3. Tiếp theo, ta sử dụng một vòng lặp để đặt các phần tử của mảng vào vị trí đúng. Mục tiêu là để đảm bảo rằng `nums[i]` sẽ có giá trị bằng `i + 1` cho mọi `i`. Để làm điều này, ta sử dụng một vòng lặp `while` để thực hiện việc hoán đổi các phần tử. Trong vòng lặp này, ta kiểm tra điều kiện `nums[i] > 0` để đảm bảo rằng số đó là số dương và `nums[i] <= n` để đảm bảo rằng số đó không vượt quá độ dài của mảng. Nếu điều kiện thoả mãn và `nums[i]` khác `nums[nums[i] – 1]`, ta hoán đổi giá trị `nums[i]` và `nums[nums[i] – 1]`. Quá trình này được lặp lại cho đến khi mọi phần tử đều được đặt vào vị trí đúng.

4. Sau khi hoàn thành vòng lặp trên, ta sử dụng một vòng lặp khác để kiểm tra xem phần tử nào không thỏa mãn điều kiện `nums[i] = i + 1`. Khi tìm thấy phần tử đầu tiên không thỏa mãn, ta trả về giá trị `i + 1` là số nguyên dương nhỏ nhất bị thiếu.

5. Nếu không tìm thấy phần tử nào không thỏa mãn trong vòng lặp trên, tức là tất cả các số từ 1 đến `n` đều có mặt trong mảng, ta trả về giá trị `n + 1` là số nguyên dương tiếp theo sau `n`.

Thuật toán trên sử dụng phương pháp đặt các phần tử vào vị trí đúng để tìm số nguyên dương nhỏ nhất bị thiếu trong mảng. Quá trình này được thực hiện bằng cách sử dụng vòng lặp và hoán đổi các phần tử để đảm bảo rằng `nums[i]` có giá trị bằng `i + 1` cho mọi `i`. Sau đó, ta kiểm tra xem phần tử nào không thỏa mãn để tìm và trả về số nguyên dương nhỏ nhất bị thiếu. Nếu không có phần tử nào không thỏa mãn, ta trả về số nguyên dương tiếp theo sau `n`.

Giải thích thuật toán bằng Java

class Solution {
  public int firstMissingPositive(int[] nums) {
    final int n = nums.length;

    // Correct slot:
    // nums[i] = i + 1
    // nums[i] - 1 = i
    // nums[nums[i] - 1] = nums[i]
    for (int i = 0; i < n; ++i)
      while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])
        swap(nums, i, nums[i] - 1);

    for (int i = 0; i < n; ++i)
      if (nums[i] != i + 1)
        return i + 1;

    return n + 1;
  }

  private void swap(int[] nums, int i, int j) {
    final int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def firstMissingPositive(self, nums: List[int]) -> int:
    n = len(nums)

    # Correct slot:
    # nums[i] = i + 1
    # nums[i] - 1 = i
    # nums[nums[i] - 1] = nums[i]
    for i in range(n):
      while nums[i] > 0 and nums[i] <= n and nums[nums[i] - 1] != nums[i]:
        nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

    for i, num in enumerate(nums):
      if num != i + 1:
        return i + 1

    return n + 1