7
Nguồn: Phỏng vấn Microsoft Câu hỏiTìm các yếu tố không trùng lặp trong một mảng được sắp xếp
Cho một mảng được sắp xếp, trong đó mọi phần tử có mặt hai lần trừ một trong đó có mặt lần duy nhất, chúng ta cần phải tìm yếu tố đó .
Bây giờ một O tiêu chuẩn (n) Giải pháp là để làm một XOR của danh sách, mà sẽ trở lại các yếu tố không trùng lặp (vì tất cả các yếu tố lặp lại hủy bỏ ra.)
Có thể giải quyết việc này một cách nhanh chóng hơn nếu chúng ta biết mảng được sắp xếp?
Thực hiện tìm kiếm nhị phân "" (thay vì traversal) trên mảng, kiểm tra cả hai hàng xóm, nếu bot khác với giá trị trung bình, bạn có giải pháp. Đây là 'O (log n)'. –
@ H2CO3 như thế nào? Chẳng phải hàng xóm luôn khác nhau sao? –
@ZiyaoWei Nopeeeee! Tôi không nói tiếng Anh. Nếu mảng được sắp xếp, ('1 1 2 2 3 4 4'), thì một hàng xóm giống với giá trị trung tâm. –