🎯 Nâng cao thuật toán di chuyển số 0 trong mảng

🧩 Vấn đề

Trong lập trình, một bài toán phổ biến là di chuyển tất cả các số 0 trong mảng về cuối mà không làm thay đổi thứ tự tương đối của các phần tử khác. Ví dụ với mảng [0, 1, 0, 3, 12], kết quả mong muốn là [1, 3, 12, 0, 0].

Điều kiện:

• Giữ nguyên thứ tự tương đối của các phần tử không phải là số 0
• Thực hiện trong mảng gốc (O(1) không gian)
• Thích hợp với một lần duyệt (O(n) thời gian)

💡 Giải pháp: Kỹ thuật hai con trỏ

Một cách hiệu quả để giải quyết bài toán này là sử dụng hai con trỏ. Dưới đây là đoạn mã Java cho giải pháp này:

public class MoveZeros {
    public static void moveZeroes(int[] nums) {
        int left = 0; // vị trí để đặt phần tử không phải là 0 tiếp theo

        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != 0) {
                // Hoán đổi phần tử không phải là 0 với vị trí con trỏ left
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++; // di chuyển đến vị trí tiếp theo cho phần tử không phải là 0
            }
        }
    }
}

🔍 Theo dõi từng bước

Mảng ban đầu: [0, 1, 0, 3, 12]

• Bước 1: right=0, nums[0]=0
  ❌ Bỏ qua (số 0)
  Mảng: [0, 1, 0, 3, 12], left=0

• Bước 2: right=1, nums[1]=1
  ✅ Hoán đổi vị trí 0↔1, left++
  Mảng: [1, 0, 0, 3, 12], left=1

• Bước 3: right=2, nums[2]=0
  ❌ Bỏ qua (số 0)
  Mảng: [1, 0, 0, 3, 12], left=1

• Bước 4: right=3, nums[3]=3
  ✅ Hoán đổi vị trí 1↔3, left++
  Mảng: [1, 3, 0, 0, 12], left=2

• Bước 5: right=4, nums[4]=12
  ✅ Hoán đổi vị trí 2↔4, left++
  Mảng: [1, 3, 12, 0, 0], left=3

Kết quả cuối cùng: [1, 3, 12, 0, 0] ✨

🧠 Thấu hiểu chính: Định lý bất biến

"Mọi thứ trước left chỉ chứa các phần tử không phải là 0 theo thứ tự tương đối ban đầu của chúng."

Điều này được đảm bảo bởi thuật toán:

• 🎯 left chỉ di chuyển khi chúng ta đặt một phần tử không phải là 0
• ➡️ Chúng ta xử lý các phần tử từ trái sang phải (giữ nguyên thứ tự)
• 📍 Mỗi phần tử không phải là 0 sẽ được đặt vào vị trí tiếp theo có sẵn
• 🚧 left hoạt động như một ranh giới: "phần đã hoàn thành" so với "công việc đang tiến hành"

⚠️ Cách sai thường gặp: Không nên đặt left++ ở đâu

// ❌ SAI - Điều này sẽ phá hủy mọi thứ!
for (int right = 0; right < nums.length; right++) {
    if (nums[right] != 0) {
        swap(nums[left], nums[right]);
    }
    left++; // ⚠️ VỊ TRÍ SAI - tăng ngay cả cho số 0!
}

Tại sao điều này thất bại:

• left tiến lên ngay cả khi gặp số 0
• Chúng ta mất dấu vị trí để đặt các phần tử không phải là 0
• Kết quả: 0, 1, 0, 3, 12 💥

Cách khắc phục: left++ phải nằm trong khối if!

🔧 Hai trường hợp hoán đổi

• Trường hợp A: left == right

// Hoán đổi phần tử với chính nó - không có thay đổi thị giác
nums[2] ↔ nums[2]  // Không có tác động

• Trường hợp B: left < right

// Hoán đổi phần tử không phải là 0 với số 0 ở bên trái
nums[1] ↔ nums[3]  // 0 ↔ 3 = di chuyển 3 về phía trước, 0 về phía sau

📊 Phân tích thuật toán

• Độ phức tạp thời gian: O(n)
  → Duyệt một lần qua mảng với công việc không đổi cho mỗi phần tử
• Độ phức tạp không gian: O(1)
  → Chỉ sử dụng hai biến con trỏ (left, right)
• Tính ổn định: ✅ Có
  → Giữ nguyên thứ tự tương đối của các phần tử không phải là 0
• Trong mảng: ✅ Có
  → Thay đổi mảng gốc mà không cần không gian thêm

🎨 Nhận diện mẫu: Phân vùng hai con trỏ

Thuật toán này theo mẫu phân vùng:

• 🎯 Một con trỏ (left) giữ phần "tốt"
• 🔍 Con trỏ khác (right) tìm kiếm các phần tử cho phần "tốt"
• 🔄 Chúng ta xây dựng kết quả theo từng bước

Các vấn đề tương tự:

• Di chuyển các số âm sang bên trái
• Tách biệt các số chẵn/lẻ
• Cờ quốc gia Hà Lan (phân vùng 3 chiều)

💭 Mô hình tư duy

Hãy nghĩ về left như một con trỏ với quy tắc đơn giản:
"Mọi thứ trước tôi chính xác là những gì chúng ta muốn trong kết quả cuối cùng."

Khi tìm thấy một số không phải là 0 → đặt nó vào vị trí con trỏ → di chuyển con trỏ về phía trước
Khi tìm thấy một số 0 → bỏ qua nó → con trỏ giữ nguyên (chờ đợi số không phải là 0 tiếp theo)

🚀 Thực hành biến thể

Khi bạn đã thành thạo, hãy thử các bài toán liên quan:

• Xóa phần tử: Xóa tất cả các trường hợp của một giá trị
• Xóa trùng lặp: Giữ lại chỉ các phần tử duy nhất
• Sắp xếp màu sắc: Sắp xếp mảng gồm các số 0, 1 và 2
• Phân vùng mảng: Tách biệt các phần tử theo điều kiện

🎯 Những điều cần nhớ

• Hai con trỏ có thể giải quyết các vấn đề sắp xếp phức tạp một cách hiệu quả
• Định lý giúp chúng ta hiểu tại sao thuật toán hoạt động
• Vị trí của các phép toán tăng là rất quan trọng
• Nhận diện mẫu giúp giải quyết các vấn đề tương tự nhanh hơn

Câu hỏi thường gặp

1. Thuật toán này có thể áp dụng cho các bài toán nào khác?
Có, bạn có thể áp dụng quy trình tương tự để giải quyết nhiều bài toán liên quan đến phân vùng.

2. Có cách nào khác để thực hiện điều này không?
Có nhiều cách khác nhau, nhưng phương pháp hai con trỏ thường là tối ưu nhất cho bài toán này.

3. Làm thế nào để tôi có thể cải thiện thuật toán của mình?
Bạn có thể thử nghiệm với các biến thể khác nhau và tìm hiểu cách tối ưu hóa thuật toán cho các tình huống khác nhau.

Hãy cho tôi biết bạn thích thuật toán hai con trỏ nào nhất? Để lại bình luận và cùng thảo luận nhé! 💬