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!
Bài liên quan
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 ạ?
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.
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.
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)
C++ có std::map nha.
Thực ra bài này dùng
std::set
là đủ, vì chỉ cần biết có hay không.std::unordered_map
mới đúng, vìstd::map
là tree nhưstd::set
.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ị @@