01/10/2018, 15:03

Nhờ người 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

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 viết 17:13 ngày 01/10/2018

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 ạ?

HK boy viết 17:18 ngày 01/10/2018

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 viết 17:13 ngày 01/10/2018

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)

HK boy viết 17:19 ngày 01/10/2018