Mô tả
Tại cửa an ninh ga đi quốc nội sân bay Tân Sơn Nhất, nhân viên yêu cầu hành khách đưa thẻ Căn cước công dân (CCCD) qua máy quét để xác thực. Vì máy rất nhạy, nhiều khi khách rung tay hoặc quét chậm, máy đọc vang một mã hai, ba lần liên tiếp. Hệ thống ghi lại toàn bộ sự kiện quét thành một mảng số nguyên, mỗi phần tử là mã CCCD dạng số (đã rút gọn thành số nhỏ để dễ xử lý trong bài này).
Phòng kĩ thuật muốn một hàm dọn dữ liệu: nếu cùng một mã xuất hiện nhiều lần dính liền nhau, chỉ giữ lại một lần duy nhất. Các mã khác nhau đứng xen kẽ thì vẫn giữ nguyên. Bạn hãy viết hàm nhận mảng đã ghi và trả về mảng đã lọc.
Đầu vào
- Một mảng số nguyên
acónphần tử (0 ≤ n ≤ 10^5), mỗi phần tử là một mã CCCD rút gọn,0 ≤ a[i] ≤ 10^9.
Đầu ra
- Trả về một mảng số nguyên mới đã khử trùng liền kề, giữ đúng thứ tự xuất hiện ban đầu.
Ràng buộc
0 ≤ n ≤ 10^5.0 ≤ a[i] ≤ 10^9.- Cần xử lý trong thời gian tuyến tính, bộ nhớ phụ tối ưu.
Ví dụ
Ví dụ 1
Đầu vào: [1, 1, 2, 2, 2, 3]
Giải thích: Mã 1 bị quét hai lần liền, giữ một. Mã 2 bị quét ba lần liền, giữ một. Mã 3 đứng một mình, giữ nguyên.
Kết quả: [1, 2, 3].
Ví dụ 2
Đầu vào: [7, 7, 7, 7]
Giải thích: Cả bốn lần quét đều là mã 7, chỉ giữ lại một.
Kết quả: [7].
Ví dụ 3
Đầu vào: [5, 6, 5, 6]
Giải thích: Các mã xen kẽ nhau, không có cụm trùng liền kề, giữ nguyên toàn bộ.
Kết quả: [5, 6, 5, 6].