[Mỗi ngày 1 thuật toán] – Tìm số chỉ xuất hiện 1 lần trong mảng

Tiếp nỗi chuỗi series “Mỗi ngày 1 thuật toán” là bài toán Tìm số chỉ xuất hiện 1 lần trong mảng. Để giải bài toán này, CodeGym sẽ cung cấp cho bạn bốn đoạn mã nguồn quan trọng, bao gồm: Pseudo-code, Java, PHP và Python. Thuật toán này khá quan trọng với nhiều ứng dụng thực tế và trong các cuộc phỏng vấn công nghệ. Hãy cùng CodeGym khám phá cách giải quyết bài toán tìm số chỉ xuất hiện 1 lần trong mảng này nhé.

Mô tả bài toán:

Cho một mảng các số nguyên, toàn bộ các số đều xuất hiện 2 lần, ngoại trừ một số duy nhất chỉ xuất hiện 1 lần. Hãy viết thuật toán để tìm ra số đó.

Ví dụ:

• Đầu vào: [2, 3, 5, 4, 5, 3, 4]
• Đầu ra: 2 (Vì chỉ có số 2 xuất hiện một lần trong mảng)

Cách tiếp cận: Để giải quyết bài toán này, ta có thể sử dụng phương pháp XOR (Exclusive OR) để tìm số khác biệt trong mảng. Phép XOR có tính chất:

• a ^ a = 0 (một số XOR với chính nó bằng 0)
• a ^ 0 = a (một số XOR với 0 bằng chính nó)
• Phép XOR có tính giao hoán và kết hợp.

Với tính chất này, nếu chúng ta XOR tất cả các phần tử trong mảng, các số xuất hiện hai lần sẽ triệt tiêu lẫn nhau, và kết quả cuối cùng sẽ là số xuất hiện một lần.

Pseudo-code

Mã nguồn Java

Mã nguồn PHP

Mã nguồn Python

Câu hỏi: Nếu không sử dụng phép toán XOR thì bạn có cách nào khác không?

Xem thêm các bài viết thú vị về Thuật toán tại đây!