Mô tả bài toán:

Cho một mảng số nguyên nums có đúng hai phần tử chỉ xuất hiện một lần, tất cả các phần tử còn lại đều xuất hiện đúng hai lần. Hãy tìm hai phần tử đó. Bạn có thể trả về kết quả theo bất kỳ thứ tự nào.

Bạn phải thiết kế một thuật toán với độ phức tạp thời gian tuyến tính và chỉ sử dụng bộ nhớ phụ hằng số.

Ví dụ 1:

<strong>Đầu vào:</strong> nums = [1,2,1,3,2,5]
<strong>Đầu ra:</strong> [3,5]
<strong>Giải thích:</strong> [5, 3] cũng là đáp án hợp lệ.

Ví dụ 2:

<strong>Đầu vào:</strong> nums = [-1,0]
<strong>Đầu ra:</strong> [-1,0]

Ví dụ 3:

<strong>Đầu vào:</strong> nums = [0,1]
<strong>Đầu ra:</strong> [1,0]

Ràng buộc:

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• Ngoại trừ hai số nguyên xuất hiện một lần, tất cả các số khác trong nums đều xuất hiện hai lần

Cách tiếp cận

1. Gọi hai số cần tìm là a và b. Vì các số còn lại xuất hiện hai lần, khi XOR toàn bộ mảng, ta thu được x = a ^ b. Do a ≠ b nên x ≠ 0, nghĩa là trong biểu diễn nhị phân của x tồn tại ít nhất một bit bằng 1 (không kể bit dấu).

2. Dùng phép tính x & (-x) để lấy bit 1 đầu tiên từ phải sang trái (bit có trọng số thấp nhất). Ví dụ: 3 = 112, -3 là bù 2 của 3 nên 3 & (-3) = 1. Nguyên lý: bit 1 thấp nhất trong x sau khi lấy bù 2 vẫn giữ nguyên, các bit cao hơn bị đảo và cộng thêm 1, nhờ đó (-x) chỉ giữ lại duy nhất bit thấp nhất đó.

3. Đặt mask = x & (-x). Bit này đại diện cho vị trí thứ i nơi a và b khác nhau (một số có bit 0, số kia có bit 1).

4. Với mỗi số num trong mảng, xét num & mask:

• Kết quả sẽ khác nhau giữa a và b.
• Các số xuất hiện hai lần luôn cho cùng kết quả vì chúng giống hệt nhau.

Do đó, ta có thể chia mảng thành hai nhóm: nhóm chứa a và các số cặp, nhóm chứa b và các số cặp. XOR từng nhóm sẽ thu được a và b.

Code triển khai

Java:

class Solution {
    public int[] singleNumber(int[] nums) {
        int xorAll = 0;
        for (int num : nums) {
            xorAll ^= num;
        }
        int mask = xorAll & (-xorAll);
        int result1 = 0, result2 = 0;
        for (int num : nums) {
            if ((num & mask) != 0) {
                result1 ^= num;
            } else {
                result2 ^= num;
            }
        }
        return new int[]{result1, result2};
    }
}

Python:

class Solution:
    def singleNumber(self, nums):
        xor_all = 0
        for num in nums:
            xor_all ^= num
        mask = xor_all & -xor_all
        group_a = 0
        group_b = 0
        for num in nums:
            if num & mask:
                group_a ^= num
            else:
                group_b ^= num
        return [group_a, group_b]