Witam, mam problem dotyczący porównywania 2 liczb, mianowicie muszę znaleźć miejsce przecięcia 2 zbiorów, które mogą posiadać do 10 000 elementów. Problem polega na tym, że prymitywny algorytm wykona ok 100 000 000 porównań. Dodam, że oba ciągi są rosnące i elementy w każdym z ciągów nie mogą sie powtarczać tzn w ciągu nr 1 nie może być 2 razy tej samej liczby.
0
4
Włóż te liczby do zbiorów a potem je przetnij? o_O W HashSet zrobisz to średnio w O(n).
Ale możesz też zrobić to szybciej skoro masz posortowane ciągi. Po prostu przesuwasz sie licznikiem po obu zbiorach jednocześnie, tzn przesuwasz w każdym kroku licznik pokazujący na mniejszy element ciągu i porównujesz tylko elementy pokazywane przez liczniki. Wyobraź sobie że jak wskaźnik przeskoczy dany element ciągu to ten element "znika". Możesz porównywać ze sobą tylko głowy swoich ciągów. Przesuwasz zawsze wskaźnik który pokazuje na element mniejszy.
Cool story: takie zadanie z wykorzystaniem dwóch list jednokierunkowych mieliśmy na 1 roku na jednej z 15 minutowych kartkówek...
Demonstracja:
c1 = 1,2,3,4,5,9
c2 = 3,5,7,9
Wskaźniki pokazują na pierwsze elementy ciągu
c1[0] ? c2[0] - różne, przesuwamy mniejszy czyli c1
c1[1] ? c2[0] - różne, przesuwamy mniejszy czyli c1
c1[2] ? c2[0] - równe, zapisujemy sobie tą wartość do przecięcia, przesuwamy oba wskaźniki
c1[3] ? c2[1] - różne, przesuwamy mniejszy czyli c1
c1[4] ? c2[1] - równe, zapisujemy sobie tą wartość do przecięcia, przesuwamy oba wskaźniki
c1[5] ? c2[2] - różne, przesuwamy mniejszy czyli c2
c1[5] ? c2[3] -równe, zapisujemy sobie tą wartość do przecięcia, przesuwamy oba wskaźniki
Przynajmniej jeden z ciągów sie skończył więc koniec algorytmu, wynik [3, 5, 9]
0
Dzięki wielkie, o to mi chodziło.
Potrzebne było mi to do pracy domowej- technikum 3 klasa.