30 ngày chống COVID cùng Leetcode | Ngày 04
Đề bài ngày hôm nay là chuyển tất cả các số 0 trong mảng 1 chiều xuống dưới cùng nhưng không đổi thứ tự các số khác 0, và không được dùng swap hai số trong mảng.
Bài toán này không phải áp dụng thuật toán gì cả, nó thiên về kỹ năng xử lý linh hoạt hơn.
Có thể có nhiều cách để giải quyết bài toán này, tôi tìm được một giải pháp độ phức tạp O(n) thời gian, tôi nghĩ thế là khá hoàn hảo rồi.
Đầu tiên khởi tạo một biến tail=0, sẽ là nơi kết thúc đoạn mảng có số khác 0, duyệt trên mảng, nếu phần từ arr[i] có giá trị bằng 0, ta sẽ cập nhật lại đoạn [0,tail] bằng: arr[tail]=arr[i], và tail sau đó sẽ tăng thêm 1 đơn vị để trờ phẩn tử tiếp theo.
Như thế ta đã có đoạn mảng toàn chữ số khác 0 trên đầu có giữ thứ tự, và chỉ số tail chính là ranh giới giữa hai đoạn mảng có 0 và không có 0.
Cuối cùng ta chỉ cần chạy vòng lặp từ tail đến cuối mảng, fill nó bằng 0 là xong.
Hết rồi, hẹn Leetcode vào ngày mai. Cảm ơn.
Bài toán này không phải áp dụng thuật toán gì cả, nó thiên về kỹ năng xử lý linh hoạt hơn.
Có thể có nhiều cách để giải quyết bài toán này, tôi tìm được một giải pháp độ phức tạp O(n) thời gian, tôi nghĩ thế là khá hoàn hảo rồi.
Đầu tiên khởi tạo một biến tail=0, sẽ là nơi kết thúc đoạn mảng có số khác 0, duyệt trên mảng, nếu phần từ arr[i] có giá trị bằng 0, ta sẽ cập nhật lại đoạn [0,tail] bằng: arr[tail]=arr[i], và tail sau đó sẽ tăng thêm 1 đơn vị để trờ phẩn tử tiếp theo.
Như thế ta đã có đoạn mảng toàn chữ số khác 0 trên đầu có giữ thứ tự, và chỉ số tail chính là ranh giới giữa hai đoạn mảng có 0 và không có 0.
Cuối cùng ta chỉ cần chạy vòng lặp từ tail đến cuối mảng, fill nó bằng 0 là xong.
Hết rồi, hẹn Leetcode vào ngày mai. Cảm ơn.
Nhận xét
Đăng nhận xét