Viết chương trình tìm số chỉ xuất hiện 1 lần trong dãy

[socola]

mọi người cho e hơi cách và hướng làm bài này với ạ.
em cảm ơn mọi người.

[nguyenchiemminhvu (NCMV)]

Mình nghĩ được cách đơn giản nhưng không tối ưu lắm, bạn sắp xếp mảng, sau đó bạn dùng 1 slide window với độ dài 3 phần tử.

Với mỗi 3 phần tử được lấy ra arr[i], arr[i + 1] và arr[i + 2], bạn tìm cách lấy ra số riêng lẻ trong 3 phần tử đó nha. Có nhiều cách, ví dụ:

(arr[i] |= arr[i + 1]) || (arr[i + 1] != arr[i + 2])
hoặc
(arr[i] + arr[i + 1] + arr[i + 2]) / 3 != arr[i] 
hoặc
(arr[i] ^ arr[i + 1]) | (arr[i + 1] ^ arr[i + 2]) != 0

Trường hợp nếu duyệt mảng đến arr[arr.size() - 2] rồi mà ko tìm thấy phần tử riêng lẻ, thì phần tử cuối cùng là đáp án.

Về việc sử dụng slide window trong mảng, bạn có thể làm tương tự như vậy:

for (int i = 2; i < arr.size(); i += 3)
{
    // tìm được phần tử riêng lẻ trong arr[i - 2] arr[i - 1] arr[i]
    // thì return kết quả
}

// return phần tử cuối cùng của mảng

[Nguyen_Nhan_Tinh (bình thường)]

bạn thử cách này xem

void find_unique() {
    int list[10] = { 1, 1, 1, 4, 4, 4, 3, 2, 2, 2 };
    std::unordered_map<int, unsigned> occurrences;
    unsigned const size = sizeof(list) / sizeof(list[0]);

    for (unsigned i = 0; i < size; ++i)
        ++occurrences[list[i]];

    for (unsigned i = 0; i < size; ++i)
        if (occurrences[list[i]] == 1)
            std::cout << list[i] << std::endl;
}