1

この形式の範囲の 2 つの配列があります。

wanted = {[10, 15], [20, 25]}
cut = {[5, 12], [22, 24]}

wantedと の 2 つの要素 (範囲) の配列も[10, 15]同様です[20, 25]。

2 つの配列はそれぞれ、次の条件を満たしています。

  1. 整数の各範囲の最初の値でソートされます
  2. 範囲が重複することはありません (たとえば[10, 15]、可能で[15, 25]はありません) 。
  3. これは、各範囲が配列内で一意であることも意味します (no [1, 5], [1, 5])
  4. 範囲がちょうど 1 つの整数の幅である場合、次のように表示されます[5, 5](開始と終了は等しい)

cutの範囲からすべての範囲が削除された範囲の配列を取得したいと考えていwantedます。

result = {[13, 15], [20, 21], [25, 25]}

以下よりも優れた/簡単/高速な素晴らしいアルゴリズムはありますか?

の各要素について、要素 from が要素 fromの上で終了するまで、wantedその要素を次の要素と比較します。cutcutwanted

4

2 に答える 2

2

nの要素wantedとmの要素があるとしますcut。

以下はO(m + n)、必要なタスクを実行するためのアルゴリズムです。

j = 1
result = {}
for i = 1:n
  // go to next cut while current cut ends before current item
  while j <= m && cut[j].end < wanted[i].start
    j++
  // cut after item, thus no overlap
  if j > m || cut[j].start > wanted[i].end
    result += (wanted[i].start, wanted[i].end)
  else // overlap
    // extract from start to cut start
    if cut[j].start > wanted[i].start
      result += (wanted[i].start, cut[j].start-1)
    // extract from cut end to end
    if cut[j].end < wanted[i].end
      result += (cut[j].end+1, wanted[i].end)
      j++

O(m + n)すべての要素を調べる必要があることを証明するのはかなり簡単であるため (最悪の場合) 、漸近的には よりもうまくいくことはできないことに注意してください。

于 2013-05-17T07:58:51.153 に答える
0

最大のサイズは何wantedですかcut? wanted「からの最初の要素」と「からのすべて」を比較すると、cut実行時間が O(n^2) かかります。つまり、配列が大きい場合は非常に遅くなります。

「マージ」のように、両方の最後に到達するまで、各配列を並行して処理する方がはるかに高速です。

于 2013-05-16T18:56:34.680 に答える