Znalezienie elementu wystepujacego w kazdej tablicy

Potrzebna pomoc
1

Witam,
Mam problem ze znalezieniem elementu wystepujacego w kazdej tablicy.
A konkretnie tablica wejsciowa wyglada np tak:
> a = [[573, 574], [573, 574], [573], [573, 574]]

Teraz potrzebuje wydobyc tylko “573” bo wystepuje w kazdej z tablic. Ktos ma pomysł jak to zrobic ?

2 
def find_common_number(arrays)
  counters = Hash.new(0)
  arrays.each do |array|
    array.each do |number|
      counters[number] += 1
    end
  end

  entry = counters.find { |_, v| v == arrays.size }
  entry ? entry[0] : nil
end

find_common_number([[573, 574], [573, 574], [573], [573, 574]])

Algorytm poprawny przy założeniu, że elementy w tablicy się nie powtarzają (w przeciwnym wypadku wymaga przeróbki). Złożoność O(n), gdzie n to sumaryczna liczba elementów we wszystkich tablicach.

W sumie dałoby się go jeszcze trochę podrasować by przerywać poszukiwanie w n-tym kroku gdy już wiadomo że nie ma elementu który występowałby we wszystkich dotychczasowych n tablicach.

3

Może coś w tym stylu?

a.reduce { |array1, array2| array1 & array2 }

Jeśli to zawsze ma być jeden element to potem można na wyniku wywołać first

3 Likes
4

Znalazlem w miedzyczasie takie cos:

a.flatten.uniq.select{|x| a.map{|y| y.include? x}.all?}

Nada sie ?

1 Like
5

@maykazw Znajdujesz jakiś losowy kawałek z neta i nas się pytasz czy się nada? Uruchom go i sobie sprawdź…

6

Mój pomysł jest taki, żeby zamienić tablice wewnętrzne na zbiory (klasa Set), bo kolejność elementów nie gra tu roli, za to będzie przeprowadzone działanie typowe dla zbiorów, czyli szukanie wspólnego elementu.

require "set"
a.map(&:to_set).reduce(:&).first

Nie wiem jaka złożoność.

7

Najprosze rozwiązanie, które działa. Można nawet skrócić do:

 a.reduce(:&)
 => [573]
2 Likes