Gợi ý cách làm hay hơn trong bài toán "Tìm những phần tử tồn tại trong cả hai danh sách A,B"

MinhHoang1601 · June 9, 2018, 5:50pm

ĐỀ: Cho hai danh sách liên kết A và B có m và n phần tử. Các phần tử trong mỗi danh sách khác nhau từng đôi một. Tìm những giá trị cùng xuất hiện trên hai danh sách. Mở rộng: giả sử có phần tử trùng.
Cách làm của mình: Mình sẽ lấy từng phần tử ds B so sánh với tất cả các phần tử của ds A. Nếu phần tử đang xét ấy tồn tại trong ds A thì xóa phần tử ấy trong ds A(xóa luôn những phần tử trùng nhau). Cứ tiếp tục làm như vậy cho đến khi xét hết số phần tử của ds B.
Mình thấy cách mình dùng nhiều vòng lặp nên chi phí nhiều. Các bạn gợi ý cho mình những cách làm tốn ít chi phí hơn nhé.

Gio · January 22, 2016, 3:15pm

sắp xếp theo một thứ tự nào đó 2 danh sách, sau đó tìm phần tử trùng nhau theo kiểu merge sort

answer=new List
if  curA.value < curB.value then
    curA=curA.next
else if curA.value> curB.value then
    curB=curB.next
else 
    begin
    answer.push(curA.value)
    curA=curA.next
    curB=curB.next
    end

Độ phức tạp = DPT thuật toán sắp xếp listA + listB