Move Zeroes

Q: Độ phức tạp thời gian của bài toán Move Zeroes là bao nhiêu?

O(n) : cả hai cách đều đọc mỗi phần tử một lần. Việc sao chép các giá trị khác không vào một mảng mới cần thêm bộ nhớ O(n) , còn cách hoán đổi bằng hai con trỏ hoạt động ngay trong mảng và chỉ cần thêm bộ nhớ O(1) .

DễHai con trỏ

+10

Bạn có một mảng số nguyên nums. Hãy chuyển mọi số 0 đến cuối mảng và giữ nguyên thứ tự của các giá trị còn lại. Trả về mảng đã sắp xếp lại, có cùng độ dài với nums.

Hàm

moveZeroes(nums: integer-array) → integer-array

numsinteger-array: mảng số nguyên cần sắp xếp lại
Trả vềinteger-array: các số khác 0 ở trước theo thứ tự ban đầu, và mọi số 0 ở cuối

Ràng buộc

1 ≤ nums.length ≤ 5000
-10⁵ ≤ nums[i] ≤ 10⁵

Ví dụ

Đầu vào: nums = [0, 4, 0, 7, 2]
Đầu ra: [4, 7, 2, 0, 0]
Giải thích: Các giá trị khác 0 là 4, 7 và 2, chúng vẫn giữ nguyên thứ tự ở phía trước. Hai số 0 chiếm hai vị trí cuối cùng.

Câu hỏi mở rộng

Bạn có thể chuyển mọi số 0 lên đầu, giữ nguyên thứ tự các giá trị khác, chỉ với một lượt duyệt và dùng thêm bộ nhớ O(1) không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Ràng buộc là giữ các giá trị còn lại theo thứ tự ban đầu, nên không thể đổi chỗ từng số 0 với phần tử cuối cùng. Một chỉ số đọc từng phần tử, chỉ số thứ hai đánh dấu vị trí của giá trị khác 0 tiếp theo, và chỉ cần một lượt duyệt để hoàn thành việc này ngay tại chỗ.

Sao chép các giá trị khác 0

Ý tưởng

Sao chép từng giá trị khác 0 vào một mảng mới theo thứ tự bạn gặp chúng, sau đó thêm các số 0 cho đến khi mảng mới dài bằng nums. Thứ tự được giữ nguyên vì bạn sao chép các giá trị theo thứ tự đọc chúng.

Mỗi phần tử được đọc một lần và ghi một lần: thời gian O(n), cộng thêm bộ nhớ O(n) cho mảng thứ hai.

Thuật toán

Tạo một mảng kết quả rỗng.
Với mỗi giá trị trong nums, hãy thêm giá trị đó vào kết quả nếu nó khác 0.
Thêm các số 0 cho đến khi kết quả có số phần tử bằng với nums.
Trả về kết quả.

def moveZeroes(nums):
    result = [x for x in nums if x != 0]
    result += [0] * (len(nums) - len(result))
    return result

Hai con trỏ, hoán đổi tại chỗ

Ý tưởng

Sau mỗi bước, hai sự thật luôn đúng: mọi giá trị trước write đều là các giá trị khác 0 đã gặp, theo đúng thứ tự, và mọi giá trị từ write đến read đều bằng 0. Một giá trị nums[read] khác 0 sẽ đổi chỗ với nums[write], nên giá trị nằm ở read là 0, hoặc vẫn là giá trị đó nếu hai chỉ số bằng nhau. Các giá trị khác 0 chỉ vượt qua số 0, không bao giờ vượt qua nhau, nên thứ tự của chúng được giữ nguyên.

Với [0, 4, 0, 7, 2], lần lượt 4, 7 và 2 đổi chỗ để vào các chỉ số 0, 1 và 2, còn các số 0 kết thúc ở chỉ số 3 và 4. Chỉ cần duyệt một lần, không cần mảng thứ hai: thời gian O(n) và bộ nhớ O(1).

Thuật toán

Đặt write thành 0.
Di chuyển read từ chỉ số đầu tiên đến chỉ số cuối cùng.
Nếu nums[read] không phải là 0, hãy hoán đổi nums[read] với nums[write], sau đó tăng write thêm 1.
Trả về nums.

def moveZeroes(nums):
    write = 0  # nums[:write] holds the non-zero values found so far, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

Lỗi thường gặp và trường hợp biên

Đổi từng số 0 với phần tử cuối cùng. Cách này di chuyển các số 0 nhưng làm xáo trộn thứ tự các phần tử còn lại: [0, 4, 7] trở thành [7, 4, 0].
Xóa các số 0 trong khi chỉ số di chuyển qua mảng. Trong [0, 0, 5], xóa chỉ số 0 sẽ đẩy số 0 thứ hai vào chỉ số 0, trong khi vòng lặp chuyển sang chỉ số 1. Mỗi lần xóa cũng làm dịch chuyển phần còn lại của mảng, khiến vòng lặp có độ phức tạp O(n²).
Kiểm tra x > 0 thay vì x != 0. Các giá trị âm không phải là số 0: [-1, 0, -2] phải trở thành [-1, -2, 0], nhưng phiên bản sao chép sẽ trả về [0, 0, 0].

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

Độ phức tạp thời gian của bài toán Move Zeroes là bao nhiêu?

O(n): cả hai cách đều đọc mỗi phần tử một lần. Việc sao chép các giá trị khác không vào một mảng mới cần thêm bộ nhớ O(n), còn cách hoán đổi bằng hai con trỏ hoạt động ngay trong mảng và chỉ cần thêm bộ nhớ O(1).

Có thể giải bài Move Zeroes với ít thao tác ghi hơn không?

Đúng vậy. Thay vì hoán đổi, hãy sao chép từng giá trị khác 0 vào nums[write], rồi sau khi quét xong, điền 0 vào mọi vị trí từ write đến cuối. Cách này chỉ ghi vào mỗi vị trí tối đa một lần. Bạn cũng có thể bỏ qua thao tác hoán đổi khi read bằng write, vì thao tác đó sẽ đặt giá trị trở lại đúng vị trí vốn có.

Vì sao Move Zeroes là bài toán hai con trỏ?

Một con trỏ đọc từng phần tử, còn con trỏ kia đánh dấu điểm kết thúc của phần đầu đã hoàn tất. Cả hai chỉ di chuyển về phía trước, nên cùng nhau tạo thành một lượt duyệt. Cách đọc và ghi tương tự giúp loại bỏ phần tử trùng lặp khỏi mảng đã sắp xếp hoặc lọc bất kỳ giá trị nào khỏi mảng ngay tại chỗ.

def moveZeroes(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [0, 4, 0, 7, 2]

Đầu ra mong đợi

[4, 7, 2, 0, 0]