何番の数字がXですか？

Question

[10,42,45,45,61,61,75,90,1240]のような配列が与えられている場合、どのような数のXがあるのか​​をどのようにして見つけることができますか？たとえば、X = 59の場合、回答は[45,45,61,61]になります。

選択列挙子はこれには完璧だと思われますが、いずれの側でもすべての要素を選択する方法を理解できません。

Answer 1

境界の繰り返し値が必要なようですね。例として機能的なアプローチがあります。これはO（n）なので、大きな入力配列を持っている場合には、O（log（n））の二等分アルゴリズムを使用する方がよいでしょう（注記：チェックする値はxs.minとxs.maxの間でなければなりません）。

xs = [10,42,45,45,61,61,75,90,1240] 
chk_pairs = xs.chunk { |x| x }.each_cons(2) 
boundaries = chk_pairs.detect { |_, (y, ys)| y > 59 }.flat_map { |x, xs| xs } 
#=> [45, 45, 61, 61] 

Answer 2

入力配列が常にソートされていると仮定すると、バイナリ検索を使用して次の下位および上位（またはおそらく等しい）番号を見つけることができます。あなたの特定のケースでは、明らかにそこから左右に目を通して、最初に見つかった次の下位/上位に等しい数字をすべて見つけます。