Sự ám ảnh của tôi với LeetCode 41: Khám phá sâu bài toán số dương đầu tiên bị thiếu

Bài toán "First Missing Positive" (số 41) trên LeetCode đã trở thành niềm đam mê lập trình mới nhất của tôi. Đó là một bài toán tưởng chừng đơn giản nhưng lại vô cùng cuốn hút, thôi thúc tôi khám phá những khía cạnh phức tạp của nó và tạo ra giải pháp TypeScript hiệu quả nhất có thể. Bài viết này không chỉ nói về việc vượt qua các cuộc phỏng vấn lập trình (mặc dù đó là một phần thưởng tuyệt vời), mà còn về niềm vui thuần túy của việc giải quyết vấn đề, sự phấn khích của tối ưu hóa và vẻ đẹp thanh lịch của mã hiệu quả. Và vì tôi là một người đam mê toán học, chúng ta thậm chí sẽ đi sâu vào nền tảng toán học của giải pháp.

Bài toán: Con sói trong bộ lông cừu

Bài toán đưa ra một mảng các số nguyên chưa được sắp xếp. Nhiệm vụ của bạn: tìm số nguyên dương nhỏ nhất bị thiếu. Có vẻ đơn giản phải không? Hãy nghĩ lại. Các ràng buộc về thời gian $O(n)$ và không gian $O(1)$ biến nhiệm vụ tưởng chừng đơn giản này thành một bài toán thuật toán đầy thách thức.

Những khó khăn ban đầu: Bẫy lực lượng vũ phu

Những nỗ lực ban đầu của tôi liên quan đến việc sắp xếp (vi phạm ràng buộc thời gian $O(n)$) và tập hợp băm (vượt quá giới hạn không gian $O(1)$). Rõ ràng, cần một phương pháp tinh vi hơn.

Khoảnh khắc Eureka: Biến đổi tại chỗ

Khái niệm then chốt là nhận ra rằng tôi có thể sử dụng chính mảng đầu vào làm bảng băm. Bằng cách sắp xếp lại các phần tử, tôi có thể đặt số $x$ ở chỉ mục $x - 1$ (nếu $1 \le x \le n$, trong đó $n$ là độ dài của mảng). Việc biến đổi tại chỗ này mở ra con đường dẫn đến một giải pháp hiệu quả.

Sự tiến hóa của mã: Một sử thi TypeScript

Đây là biên niên sử về sự tiến hóa của mã của tôi, với các giải thích chi tiết và những hiểu biết về toán học:

Phiên bản 1: Phương pháp ngây thơ (với các lần hoán đổi dư thừa)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length

  // Đặt mỗi số vào vị trí chính xác của nó nếu nó nằm trong phạm vi [1, n]
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const correctIndex = nums[i] - 1
      ;[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]] // Hoán đổi
    }
  }

  // Tìm số dương nhỏ nhất bị thiếu
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // Nếu tất cả các số đều ở vị trí chính xác, số bị thiếu là n + 1
  return n + 1
}

Phiên bản này, mặc dù hoạt động được, nhưng lại gặp phải các lần hoán đổi dư thừa. Số lần hoán đổi trong trường hợp xấu nhất gần bằng $O(n^2)$, mặc dù trường hợp trung bình gần với $O(n)$.

Giải thích:

1. Sắp xếp lại mảng: Mỗi số nums[i] được đặt ở chỉ mục "chính xác" của nó (nums[i] - 1) nếu nó nằm trong phạm vi [1, n] và chưa ở vị trí chính xác.

2. Xác định số dương bị thiếu: Sau khi sắp xếp lại, chỉ mục đầu tiên i mà nums[i] !== i + 1 cho biết rằng i + 1 là số nguyên dương bị thiếu.

3. Trả về n + 1 nếu cần: Nếu tất cả các số từ 1 đến n đều ở vị trí chính xác, số bị thiếu là n + 1.

Điểm chính:

• Sắp xếp lại tại chỗ: Chúng ta sửa đổi chính mảng để tránh sử dụng không gian thêm.
• Hiệu quả: Cả việc sắp xếp lại và quét cuối cùng đều mất thời gian $O(n)$, đảm bảo hiệu suất tối ưu.

Phiên bản 2: Tăng cường hiệu năng (Loại bỏ các lần hoán đổi dư thừa)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  // Sắp xếp lại các số vào vị trí chính xác của chúng nếu có thể
  while (idx < n) {
    const correctIdx = nums[idx] - 1
    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      // Hoán đổi mà không cần sử dụng biến tạm thời
      ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
    } else {
      idx++
    }
  }

  // Xác định số dương nhỏ nhất bị thiếu
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

Giải thích:

1. Sắp xếp lại hiệu quả:

   • Vòng lặp while hoán đổi các phần tử trực tiếp vào vị trí chính xác của chúng (nums[idx] - 1) chỉ khi số đó nằm trong phạm vi hợp lệ [1, n] và chưa ở vị trí chính xác.
   • Điều kiện if đảm bảo các số không hợp lệ hoặc đã đúng được bỏ qua mà không cần hoán đổi không cần thiết.

2. Kiểm tra chỉ mục trực tiếp:

   • Trong giai đoạn sắp xếp lại, các lần hoán đổi không hợp lệ và các thao tác dư thừa được tránh bằng cách kiểm tra phạm vi và giá trị của nums[idx].

3. Hoán đổi tiết kiệm bộ nhớ:

   • Việc sử dụng giải cấu trúc ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) loại bỏ sự cần thiết của một biến tạm thời, giảm thiểu việc sử dụng bộ nhớ.

4. Vòng lặp tối thiểu:

   • Thuật toán chỉ sử dụng hai lần quét tuyến tính:
     • Một lần để sắp xếp lại mảng tại chỗ.
     • Một lần để tìm số dương nhỏ nhất bị thiếu.

Phân tích độ phức tạp:

• Độ phức tạp về thời gian:
  • Vòng lặp while và vòng lặp for đều chạy trong $O(n)$, làm cho tổng độ phức tạp về thời gian là $O(n)$.
• Độ phức tạp về không gian:
  • Thuật toán hoạt động tại chỗ mà không sử dụng bất kỳ cấu trúc dữ liệu phụ trợ nào, vì vậy độ phức tạp về không gian là $O(1)$.

Tại sao mã này là tối ưu:

• Hiệu năng: Vòng lặp while được sắp xếp hợp lý đảm bảo các thao tác dư thừa tối thiểu, tối đa hóa tốc độ.
• Hiệu quả bộ nhớ: Việc sử dụng hoán đổi tại chỗ và tránh các biến phụ trợ đảm bảo dấu chân bộ nhớ thấp nhất có thể.

Phiên bản 3: Tối ưu hóa cho bộ nhớ (Sử dụng không gian tối thiểu)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  while (idx < n) {
    const correctIdx = nums[idx] - 1

    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      nums[idx] = nums[correctIdx]
      nums[correctIdx] = correctIdx + 1
    } else {
      idx++
    }
  }

  for (let idx = 0; idx < n; idx++) {
    if (nums[idx] !== idx + 1) {
      return idx + 1
    }
  }

  return nums.length + 1
}

Tối ưu hóa bộ nhớ chính:

1. Cập nhật tại chỗ với biến tạm thời tối thiểu:

   • Thay vì sử dụng biến temp để hoán đổi, mã này trực tiếp sửa đổi mảng với nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1.
   • Điều này loại bỏ sự cần thiết của một biến tạm thời, giảm thiểu chi phí bộ nhớ bằng một lượng không đổi.

2. Ít giá trị tạm thời hơn trong vòng lặp:

   • Mã tính toán correctIdx trực tiếp trong vòng lặp, tránh cần lưu trữ các biến trung gian bổ sung bên ngoài logic cốt lõi.
   • Ít phép gán biến hơn có nghĩa là việc sử dụng bộ nhớ thấp hơn một chút cho mỗi lần lặp.

3. Quét duy nhất để sắp xếp lại:

   • Không giống như mã đầu tiên sử dụng các điều kiện lồng nhau trong vòng lặp while, việc triển khai này hoàn thành các lần hoán đổi hoặc tăng chỉ mục theo cách hợp lý hơn, giảm độ sâu ngăn xếp thời gian chạy và việc sử dụng bộ nhớ.
   • Cấu trúc vòng lặp (while với một phép tăng hoặc sắp xếp lại duy nhất) trực tiếp hơn, yêu cầu ít giá trị phụ trợ hơn.

4. Không có kiểm tra dư thừa:

   • Các kiểm tra correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] ngắn gọn và ngăn chặn các thao tác không cần thiết có thể tạm thời sử dụng bộ nhớ ngăn xếp hoặc bộ nhớ cache CPU.
   • Điều này tránh cần phân bổ thêm tài nguyên cho các thao tác sẽ không đóng góp vào kết quả.

Tại sao điều này tạo ra sự khác biệt về bộ nhớ:

• Giảm lưu trữ tạm thời: Bằng cách không dựa vào biến temp và giảm thiểu các phép tính trung gian, dấu chân bộ nhớ nhỏ hơn.
• Thực thi hợp lý: Ít bước và logic đơn giản hơn dẫn đến việc sử dụng bộ nhớ ít hơn cho mỗi thao tác.
• Tận dụng bộ nhớ cache được cải thiện: Mô hình truy cập tuyến tính, có thể dự đoán được của thuật toán cải thiện hiệu năng bộ nhớ cache CPU, gián tiếp giảm chi phí bộ nhớ.

Giải pháp này tập trung vào việc cập nhật tại chỗ trực tiếp, sử dụng biến tối thiểu và các mô hình truy cập bộ nhớ hiệu quả làm cho nó tốt nhất về hiệu quả bộ nhớ. Mặc dù tiết kiệm là không đổi ($O(1)$), nhưng chúng đủ đáng kể để đăng ký trên các nền tảng cạnh tranh như LeetCode, đặc biệt là đối với các tập dữ liệu lớn.

Phiên bản 4: Kiệt tác được tối ưu hóa (Hoán đổi tại chỗ, không có biến tạm)

function firstMissingPositive(nums: number[]): number {
  for (let i = 0; i < nums.length; i++) {
    while (nums[i] !== i + 1) {
      if (nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]) {
        break
      }

      const temp = nums[i]
      nums[i] = nums[temp - 1]
      nums[temp - 1] = temp
    }
  }

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return nums.length + 1
}

Phiên bản cuối cùng này đạt được cả hiệu năng tối ưu và sử dụng bộ nhớ tối thiểu thông qua việc hoán đổi tại chỗ thanh lịch mà không cần biến tạm thời. Độ phức tạp về thời gian hiện chắc chắn là $O(n)$, và độ phức tạp về không gian là $O(1)$, đáp ứng tất cả các yêu cầu. Về mặt toán học, chúng ta đang thực hiện một loại hoán vị tuần hoàn trong mảng để đặt các phần tử vào vị trí "chính xác" của chúng.

Bằng cách thêm một kiểm tra (nums[i] === nums[nums[i] - 1]), chúng ta ngăn chặn các lần hoán đổi không cần thiết. Điều này cải thiện hiệu năng đáng kể, đưa độ phức tạp về thời gian gần hơn với $O(n)$ mong muốn.

Sự khác biệt chính trong việc triển khai:

1. Tránh hoán đổi dư thừa:

   • Mã được cung cấp rõ ràng kiểm tra xem nums[i] === nums[nums[i] - 1] trước khi thực hiện hoán đổi. Điều này tránh các lần hoán đổi không cần thiết khi số đó đã ở vị trí chính xác hoặc có bản sao.
   • Trong việc triển khai đầu tiên, kiểm tra này bị bỏ qua, có thể dẫn đến các lần hoán đổi dư thừa ngay cả khi không cần thiết. Mỗi lần hoán đổi bổ sung thêm chi phí, đặc biệt là đối với các mảng lớn hơn.

2. So sánh chỉ mục trực tiếp:

   • Mã được cung cấp sử dụng while (nums[i] !== i + 1) để đảm bảo một số được hoán đổi lặp đi lặp lại vào vị trí chính xác của nó cho đến khi nó được đặt đúng vị trí hoặc một điều kiện không hợp lệ được đáp ứng. Điều này loại bỏ các lần lặp vòng lặp không cần thiết.
   • Mã đầu tiên không rõ ràng so sánh số với chỉ mục dự định của nó trong điều kiện vòng lặp. Nó có thể thực hiện nhiều thao tác hơn trong trường hợp các số cần di chuyển tối thiểu.

3. Kiểm tra điều kiện được tối ưu hóa:

   • Bằng cách kết hợp các điều kiện trong một khối if duy nhất (ví dụ: nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), mã tránh chi phí bổ sung từ các kiểm tra hoặc phép tính không cần thiết.

Tại sao điều này quan trọng trong LeetCode:

• Tính nhất quán thời gian chạy:

  • Các phép đo thời gian chạy của LeetCode có thể nhạy cảm với các thao tác không cần thiết, chẳng hạn như hoán đổi dư thừa hoặc so sánh thêm.
  • Mã được cung cấp giảm thiểu các thao tác này, dẫn đến thời gian chạy nhanh hơn trung bình.

• Hiệu quả bộ nhớ cache:

  • Ít hoán đổi và logic vòng lặp đơn giản hơn dẫn đến việc sử dụng bộ nhớ cache CPU tốt hơn. Các bộ xử lý hiện đại được hưởng lợi từ các mô hình truy cập có thể dự đoán và hợp lý, mà mã được cung cấp thể hiện.

Kết quả

Đây là tóm tắt được trình bày ở định dạng bảng:

Bảng này làm nổi bật sự đánh đổi và tính tối ưu của giải pháp cuối cùng.

Tóm tắt cho thấy rằng lần thử cho hiệu năng và bộ nhớ tốt nhất thực sự là tối ưu nhất, đạt được:

• Thời gian chạy 1 ms: Khớp với kết quả nhanh nhất về hiệu năng.
• Sử dụng bộ nhớ 58,9 MB: Cao hơn một chút so với bản sao "bộ nhớ tốt nhất" nhưng thấp hơn các lần thử khác.

Phân tích:

1. Thời gian chạy:

   • Thời gian chạy 1 ms cho thấy phương pháp được tối ưu hóa loại bỏ các kiểm tra dư thừa và các lần hoán đổi không cần thiết.
   • Độ phức tạp thời gian nhất quán của $O(n)$ đảm bảo khả năng mở rộng cho các tập dữ liệu lớn hơn.

2. Bộ nhớ:

   • 58,9 MB là cạnh tranh, cho thấy dấu chân bộ nhớ thấp mặc dù thực thi nhanh. Sự gia tăng nhỏ này so với "bộ nhớ tốt nhất" (58,5 MB) có thể là do sự khác biệt trong việc giải cấu trúc hoặc tối ưu hóa cụ thể của engine.

3. Sự đánh đổi:

   • Giải pháp "bộ nhớ tốt nhất" hy sinh một chút thời gian chạy để sử dụng bộ nhớ thấp hơn.
   • Giải pháp "hiệu năng tốt nhất" tập trung nhiều hơn vào tốc độ nhưng sử dụng nhiều bộ nhớ hơn một chút.

Kết luận:

Giải pháp được tối ưu hóa tạo ra sự cân bằng tốt:

• Thời gian chạy 1 ms nhanh như mã hoạt động tốt nhất.
• Sử dụng bộ nhớ 58,9 MB gần với kết quả "bộ nhớ tốt nhất", với chi phí nhỏ.

Đó là một lựa chọn toàn diện, đặc biệt là đối với các trường hợp mà cả hiệu năng và bộ nhớ đều quan trọng.

Nền tảng toán học: Hoán vị tuần hoàn và nguyên lý chuồng chim

Ý tưởng cốt lõi xoay quanh khái niệm hoán vị tuần hoàn. Chúng ta đặt mục tiêu tạo ra một chu kỳ mà mỗi số $x$ được đặt ở chỉ mục $x - 1$. Vòng lặp while hiệu quả duyệt qua các chu kỳ này, đảm bảo mỗi phần tử tìm thấy vị trí được chỉ định của nó.

Nguyên lý chuồng chim đóng một vai trò tinh tế ở đây. Vì chúng ta có $n$ vị trí có thể (chỉ mục $0$ đến $n-1$) và chúng ta đang tìm một số nguyên dương bị thiếu trong phạm vi $[1, n+1]$, nếu tất cả các số từ 1 đến $n$ đều có mặt, số bị thiếu phải là $n + 1$.

Niềm đam mê vẫn tiếp tục...

Sự say mê của tôi với LeetCode 41 vẫn còn. Tôi liên tục tìm kiếm các tối ưu hóa sâu hơn và những hiểu biết sâu sắc hơn. Hãy cùng tôi trong cuộc tìm kiếm này! Chia sẻ suy nghĩ, giải pháp của riêng bạn và hãy cùng nhau khám phá giao điểm thanh lịch giữa toán học và thuật toán.