3

数値と値のペアで構成される配列があります。

a = [[2, :foo], [5, :bar], ..., [17, :baz]]

ここで、2 つのペアが同じ数字を持たないと仮定することができ、ペアはそれらの数字の値によってソートされます。この配列に基づいて、常に 内の最小数値と最大数値の間にあるa数値を渡し、 を超えない最大の数値とペアになっている値を返します。予想される戻り値は次のとおりです。iai

2 # => :foo
4 # => :foo
5 # => :bar
17 # => :baz

これを行う最善の方法は何ですか？ハッシュを使用すると範囲をキーとして扱うのに問題があり、caseステートメントを使用すると に動的に適用するのが困難になりますa。

4

3 に答える 3

5

対数計算量が必要な場合は、二分探索またはある種の平衡探索木を使用する必要があります。簡単にするために、私はrbtree宝石を提案します：

require 'rbtree'

a = [[2, :foo], [5, :bar], [17, :baz]]
t = RBTree[a]

t.upper_bound 4  # => [2, :foo]
t.upper_bound 5  # => [5, :bar]
t.upper_bound 1  # => nil
于 2013-02-22T13:40:38.427 に答える
3

今後の作業にRange#bsearch最適です :-) このようにして、適切なログの複雑さを得ることができます。

bsearch最大値が必要なときに最小値を見つけるように設定されているため、配列を逆にする必要があります。楽しみ：

DATA = [[2, :foo], [5, :bar], [12, :hello], [17, :baz]].reverse

def lookup(i)
  nb, val = DATA.bsearch{|nb, val| i >= nb}
  val
end

lookup 2  # => :foo
lookup 4  # => :foo
lookup 5  # => :bar
lookup 17 # => :baz

require 'backports/2.0.0':-)で今日利用可能

于 2013-02-22T16:01:59.767 に答える
1

ハッシュの問題はよくわかりませんが、あなたが正しく理解していれば、これはうまくいきます。

a = [[2, :foo], [5, :bar], [17, :baz]]
h = Hash[a]

class Hash
  def get(i)
    return nil if i < keys.min
    i -= 1 until include?(i)
    self[i]
  end
end

h.get(4) #=> :foo
h.get(5) #=> :bar
h.get(1) #=> nil # No key below 2 exists.
于 2013-02-22T13:33:12.550 に答える