0

間隔のリストが与えられた場合 (ここではインデックスとともに表示):

0: 1,3
1: 0,4
2: 5,7
3: 6,9
4: 2,8

そして、リストのインデックスから任意のインとアウトが与えられた場合、対応する包括的間隔から最小値と最大値を決定する良い方法はありますか?

例：0,4あなたに与えるでしょう0,9。 2,3あなたに与えるでしょう5,9。

私の現在の解決策では、範囲内のすべての間隔で反復処理を行い、インポイントで最小値を維持し、アウトポイントで最大値を維持します。間隔のリストが非常に長い場合にこれを高速化するために見落としているアルゴリズム技術のデータ構造があるかどうか疑問に思っています。間隔のリストは変更されないため、データを別の方法で表現するために事前に作成できるモデルがあるのではないでしょうか?

4

2 に答える 2

2

簡単な方法の 1 つは、ツリー構造を持つことです。ツリーのルートには、リスト全体の最小/最大値があります。次に、前半と後半などの最小/最大を与える2つの子を持ちます。これにより、O（log（n））検索アルゴリズムを使用できます。ここで、nは間隔リスト全体のサイズです。

まず、ツリーを作成します。これは、間隔のリストを 2 つに分割し、サブ間隔ごとにツリーを作成することで、再帰的に実行できます。

def makeTree(begin,end,intervals):
  if end==begin:
    return None
  if end==begin+1:
    return Node(begin,end,intervals[begin],None,None)
  partition=(begin+end)/2
  left=makeTree(begin,partition)
  right=makeTree(partition,end)
  range=combineRanges(rangeOf(left),rangeOf(right))
  return Node(begin,end,range,left,right)

ツリーを取得したら、ツリーのルートをこの関数に渡すことができます。

def findRange(node,begin,end):
  # If the node's range doesn't intersect the range you are looking for, 
  # then you don't have to look any deeper.
  if node is None or begin>=node.end or end<=node.begin:
    return None
  # If the node's range is completely inside the range you are looking for, then
  # you also don't need to look any deeper.
  if begin<=node.begin and end>=node.end:
    return node.range
  # Otherwise, check each child.
  left_range=findRange(node.left,begin,end)
  right_range=findRange(node.right,begin,end)
  # And return the combined result.
  return combineRanges(left_range,right_range)

間隔内の任意の x に対して begin <= x < end となるように、半分開いた間隔を使用していることに注意してください。これにより、コードが少しきれいになります。

于 2012-12-17T05:28:39.803 に答える
1

各間隔が実際に最小値と最大値を示していることが容易にわかるように。

したがって、問題は次のようになります。2 つの配列を指定し、指定されたインデックス範囲の最小値と最大値を見つけます。

最小値と最大値の検索は似ているため、ここでは最小値について説明します。

まず、前述のように、セグメント ツリーを使用して簡単に実行できます@Vaughn Cato。

実際には、 のような非常に強力なデータ構造を使用する必要はありません。Segment treeこれを解決する別の特定のアルゴリズムがあり、これはRange Minimum Queryと呼ばれます。

ところで、私はについて話している投稿を書きました。http://attiix.com/2011/08/22/4-ways-to-solve-%c2%b11-rmq/RMQを参照してください。

于 2012-12-17T08:06:03.847 に答える