Porównaj dwie tablice lub listy tablic, znajdź podobne i różne wartości.

Mam dwie tablice (lub tablice, jeśli jest to łatwiejsze) ciągów. Muszę to porównać, znaleźć, które istnieją tylko w pierwszej tablicy, które istnieją w obu, i które istnieją tylko w drugiej tablicy. Te tablice mają różną długość i mogą być w różnych rzędach. Jeśli to konieczne, prawdopodobnie mógłbym je sortować ...Porównaj dwie tablice lub listy tablic, znajdź podobne i różne wartości.

Wiem, że mogę to zhakować razem, ale myślę, że może to być dość standardowe i wydajne/"najlepsze" rozwiązanie, a ja jestem bardziej ciekawy niż cokolwiek innego.

Używam C# do tego, ale jeśli chcesz napisać swoje rozwiązanie w innym języku, każda pomoc jest mile widziane.

Dzięki za pomoc!

Źródło

2010-07-19 Wes

Czy to praca domowa? –

Spójrz na próbki Linq 101 tutaj, powinny pomóc (zwłaszcza operatorzy zestawu): http://msdn.microsoft.com/en-us/vcsharp/aa336746.aspx – andyp

Nie, to nie jest praca domowa haha. Po prostu wiem, że istnieje chłodniejszy/bardziej efektywny sposób niż to, co mogłem wymyślić w ciągu około 20 minut. Nie korzystałem wcześniej z Linq, ale może to być idealny czas na zanurzenie się w nim. dzieki za sugestie. – Wes

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;

Źródło

2010-07-19 19:24:59 Luiscencio

Oto, co wymyśliłem. Właśnie pomyślałem, że jest jakiś fajny sposób C#/.net robiący to używając porównywalnych albo coś. Podam również kilka linq, ale jeśli wszystko inne zawiedzie, to zadziała. – Wes

Należy zauważyć, że jeśli listy mają rozmiar n i m, wówczas wszystkie te rozwiązania są równe O (n * m). Istnieją znacznie bardziej wydajne rozwiązania, jeśli m i n są duże. –

Jeśli tablice są duże, należy użyć struktury danych, która jest wydajna dla tych operacji; tablice nie są.

Naiwny roztwór to O (n^2) w czasie, jeśli tablice mają rozmiar n.

Jeśli sortujesz tablice na miejscu, możesz wyszukiwać binarnie w poszukiwaniu przedmiotów; sortowanie będzie prawdopodobnie O (n lg n), a wyszukiwanie n razy kosztem lg n na wyszukiwanie będzie również O (n lg n) w czasie.

Jeśli najpierw zmienisz tablicę na HashSet<T>, możesz to zrobić w O (n) czasie i O (n) dodatkowej przestrzeni.

Źródło

2010-07-19 19:35:55

Nigdy nie użyłem hashitu, ale jestem bardzo ciekawy, zagłębię się w to, dzięki! – Wes

@Ws: 'HashSet' został wprowadzony w .NET Framework 3.5. – Brian

@Wes: @Brian: I to było nazywane HashSet zamiast bardziej sensownej nazwy "Ustaw", ponieważ ... czekać na to ... ponieważ "Set" jest * słowem kluczowym Visual Basic *. –

Porównaj dwie tablice lub listy tablic, znajdź podobne i różne wartości.

Odpowiedz

Powiązane problemy