So sánh hai mảng hoặc mảng, tìm giá trị tương tự và khác nhau

Question

Tôi có hai mảng (hoặc arraylists nếu nó dễ dàng hơn) của chuỗi. Tôi cần phải so sánh chúng, tìm thấy chỉ tồn tại trong mảng đầu tiên, tồn tại trong cả hai, và chỉ tồn tại trong mảng thứ hai. Các mảng này có độ dài khác nhau và có thể theo các thứ tự khác nhau. Nếu cần thiết, tôi cho rằng tôi có thể sắp xếp chúng ...

Tôi biết tôi có thể cùng nhau hack, nhưng tôi nghĩ điều này có thể có giải pháp khá "tiêu chuẩn và hiệu quả" và tôi tò mò hơn bất cứ thứ gì.

Tôi đang sử dụng C# cho điều này, nhưng nếu bạn muốn viết giải pháp của mình bằng ngôn ngữ khác, mọi trợ giúp đều được chào đón.

Cảm ơn sự giúp đỡ!

Answer 1

var onlyinfirst = from s in list1 where !list2.Contains(s) select s; 
var onlyinsecond = from s in list2 where !list1.Contains(s) select s; 
var onboth = from s in list1 where list2.Contains(s) select s; 

Answer 2

Nếu mảng lớn thì bạn sẽ muốn sử dụng cấu trúc dữ liệu hiệu quả cho các hoạt động này; mảng không.

Giải pháp ngây thơ là O (n^2) trong thời gian nếu các mảng có kích thước n.

Nếu bạn sắp xếp các mảng tại chỗ thì bạn có thể tìm kiếm nhị phân chúng cho các mục; phân loại có thể sẽ là O (n lg n) và tìm kiếm n lần với chi phí của lg n cho mỗi tìm kiếm cũng sẽ là O (n lg n) trong thời gian.

Nếu bạn biến từng mảng thành một số HashSet<T> trước tiên thì bạn có thể thực hiện nó trong khoảng thời gian O (n) và O (n).