Nhờ giải thích thuật toán tìm phần tử trong mảng không có cặp với các phần tử khác

[thai_tranngoc]

Em đang năm tìm hiểu về thuật toán tìm phần từ trong mảng không có cặp với các phần tử khác. Ví dụ có mảng a[0,0,2,1,3,2,1] thì output sẽ là 3. Tuy nhiên em chưa hiểu về thuật toán này trong Javascript lắm nên nhờ mọi người giải thích hộ em với ạ?

var a = [0,0,2,1,3,2,1];
function getUpaired(arr) {
    var obj = {};
    for (var i = 0; i < arr.length; i++) {
        if (typeof obj[arr[i]] !== 'undefined') {
            delete obj[arr[i]];
            continue;
        }
    obj[arr[i]] = i;
    }
    return Number(Object.keys(obj)[0]);
}
getUpaired([0,0,2,1,3,2,1]);

Em cảm ơn!

[thai_tranngoc]

Dạ em cảm ơn ạ. Tại em đang học javascript nên muốn hỏi thuật toán này chạy trong javascript ntn ạ?

[noname00 (HK boy)]

obj là 1 dict, nhiệm vụ của nó là lưu vị trí xuất hiện đầu tiên của phần tử u trong mảng a.

if (typeof obj[arr[i]] !== ‘undefined’)

Nếu trước đó đã tồn tại 1 phần tử arr[i] thì ta bỏ phần tử arr[i] hiện tại đi, vì phần tử hiện tại đã bị lặp lại (có cặp). Nếu không thì ta thêm vào dict, đánh dấu vị trí lần đầu xuất hiện của phần tử arr[i].

Cuối cùng, return trả về 1 phần tử (cụ thể là phần tử đầu tiên) trong dict, dict chỉ chứa những phần tử không có cặp trong list.

[kiencon]

Obj là 1 mảng mở rộng, ở trường hợp này nó sẽ lưu dưới dạng {key : index};
Duyệt qua mảng a,
mỗi a[i] là một key, nếu key đã tồn tại(tức phần tử bị lặp thì xóa nó đi) nếu chưa có thì add vào Obj.
Kết quả cuối cùng còn lại các giá trị key không bị lặp và index của nó.
Độ phức tạp của thằng này là O(n);
Trong C/C++ cũng làm đc điều này nhưng khó khăn hơn 1 chút vì không có dạng mảng mở rộng, thay vào đó ta có thể sử dụng bảng băm để lưu và tìm kiếm phần tử. Độ phức tạp cũng sẽ là O(n)

[noname00 (HK boy)]

Trong C/C++ cũng làm đc điều này nhưng khó khăn hơn 1 chút vì không có dạng mảng mở rộng

C++ có std::map nha.

[rogp10]

Thực ra bài này dùng std::set là đủ, vì chỉ cần biết có hay không.

C++ có std::map nha.

std::unordered_map mới đúng, vì std::map là tree như std::set.

[kiencon]

Hehe không biết đến thằng này, C++ chỉ học cơ bản về kĩ thuật lập trình rồi vô oop của nó chứ k chuyên sâu, giờ đg cày js oop, 1 ngôn ngữ quái dị @@