Xóa các bản sao trùng lặp khỏi một danh sách bằng cách so sánh với một danh sách khác

Question

Tôi có hai danh sách đối tượng và tôi muốn xóa các cá thể khỏi một danh sách có trong danh sách khác.

ví dụ: Tôi đã theo hai danh sách và giả sử mỗi chữ đại diện cho đối tượng.

Danh sách Lista = {A, B, C, D, E, F, G, H, I, J}

Danh sách listB = {D, G, K, P, Z}

Bây giờ, rõ ràng listB có D và G mà đang có trên Lista quá vì vậy tôi muốn Lista là như thế này

Lista = {A, B, C, E, F, H, I, J}

Can các bạn vui lòng đề xuất giải pháp cho điều này với O (n) hoặc ít hơn O (n2).

Tôi có thể lặp qua cả hai danh sách và xóa các trường hợp trùng lặp bằng cách so sánh nhưng tôi muốn có thứ gì đó hiệu quả hơn.

Answer 1

Bạn có thể thêm cả hai yếu tố danh sách để một Set

Để loại bỏ các yếu tố trên một danh sách từ khác, hãy thử listA.removeAll(listB);

Answer 2

Giống như ssantos trả lời, bạn có thể sử dụng một Set.

Hoặc, nếu các danh sách được sắp xếp, sau đó bạn có thể luân phiên lặp qua chúng. Lặp lại qua ListA cho đến khi bạn đạt đến phần tử lớn hơn thành phần hiện tại của ListB, sau đó lặp qua ListB cho đến khi bạn đạt đến phần tử lớn hơn phần tử hiện tại của ListA, v.v.

Answer 3

Nếu danh sách không được phân loại và là các đối tượng ArrayLists hoặc các danh sách tương tự khác với một phương thức chứa O (n), thì bạn nên tạo một HashSet với các mục của listB để thực hiện việc loại bỏ. Nếu các mục không được đưa vào một tập hợp thì bạn sẽ kết thúc với hiệu suất O (n^2).

Cách dễ nhất để làm những gì bạn cần là như sau:

listA.removeAll(new HashSet(listB)); 

ArrayList.removeAll(Collection) sẽ không đưa các mục vào một tập cho bạn (ít nhất là trong JDK 1.6 và 1.7 phiên bản tôi đã kiểm tra), đó là lý do tại sao bạn cần tự tạo HashSet ở trên.

Phương thức removeAll sẽ sao chép các mục bạn muốn giữ vào đầu danh sách khi nó vượt qua nó, tránh nén mảng với mỗi lần xóa, vì vậy sử dụng nó với một HashSet được truyền như được hiển thị là tối ưu hợp lý và là O (n).

Answer 4

Sau đây là một số giả C để giải quyết trong thời gian dự kiến ​​O(n).

lenA = length pf listA 
lenB = length of listB 
shortList = (lenA <= lenB) ? A : B 
longList = (shortList == A) ? B : A 

create hash table hashTab with elements of shortList 

for each element e in longList: 
    is e present in hashTab: 
     remove e from longList 

now, longList contains the merged duplicate-free elements