0

昇順の要素を持つキューがあるとします。つまり、head < 2nd < 3rd < ... < tail

および降順の要素を持つスタック、つまり top > 2nd > 3rd > ...

それらのサイズは最大で 1 異なります (同じサイズである可能性があります)。

スタック/キューを追加せずに、それらを同じキュー (またはスタック) にマージして、単一の並べ替えられたシーケンスとして最も効率的な方法は何ですか?

これまでのところ、私が考えた最良の方法は、基本的に選択ソートである二次アルゴリズムであり、キューとスタックが事前にソートされているという事実とそのサイズを実際に利用していないようです。私たちはもっとうまくやれるかどうか疑問に思っていますか？

4

1 に答える 1

0

その場でマージして、結果をキューの最後に配置します。カウントを維持して、いつ終了するかがわかります。これは O(n) です。

これはpythonで行います。キューまたはスタック クラスは使用していませんが、q リストは FIFO であり、s リストは LIFO であることがわかります。

出力を確認できるように、最も興味深いデバッグ ケースが有効になっています。

def sort(Q, S, debug=False):
  q = Q
  s = S
  size = len(Q) + len(S)
  handled = 0
  while handled < size:
    move_from_queue = len(s) == 0 or (len(q) > 0 and q[0] < s[0])
    last_from_stack = (handled == size-1) and (len(s) == 1)
    if move_from_queue and not last_from_stack:
      q_front = q[0]
      q = q[1:] + [q_front]
      msg = 'moved q[0]=%d to end, q=%r' % (q_front, q)
    else:
      (s_top, s) = (s[0], s[1:])
      q += [s_top]
      msg = 'popped s[0]=%d to end of q=%r,s=%r' % (s_top, q, s)
    handled += 1
    if debug:
      print 'Debug-Step %d: %s' % (handled, msg)
  return (q, s)

def test_sort(Q, S, debug=False):
  print 'Pre  Q: %r' % Q
  print 'Pre  S: %r' % S
  (Q, S) = sort(Q, S, debug)
  print 'Sorted: %r' % Q
  print

if __name__ == "__main__":
  test_sort([1, 3, 7, 9], [2, 5, 5])
  test_sort([1, 3, 7], [2, 5, 5])
  test_sort([1, 3, 7], [2, 5, 5, 9], True)
  test_sort([], [])
  test_sort([1], [])
  test_sort([], [1])

出力： 

前の質問: [1, 3, 7, 9]
プリ S: [2, 5, 5]
並べ替え: [1, 2, 3, 5, 5, 7, 9]

前質問: [1, 3, 7]
プリ S: [2, 5, 5]
並べ替え: [1, 2, 3, 5, 5, 7]

前質問: [1, 3, 7]
前S: [2, 5, 5, 9]
Debug-Step 1: q[0]=1 を末尾に移動、q=[3, 7, 1]
Debug-Step 2: s[0]=2 を q=[3, 7, 1, 2],s=[5, 5, 9] の末尾にポップ
Debug-Step 3: q[0]=3 を末尾に移動、q=[7, 1, 2, 3]
Debug-Step 4: s[0]=5 を q=[7, 1, 2, 3, 5],s=[5, 9] の末尾にポップ
Debug-Step 5: s[0]=5 を q=[7, 1, 2, 3, 5, 5],s=[9] の末尾にポップ
Debug-Step 6: q[0]=7 を末尾に移動、q=[1, 2, 3, 5, 5, 7]
デバッグ-ステップ 7: s[0]=9 を q=[1, 2, 3, 5, 5, 7, 9],s=[] の最後にポップ
並べ替え: [1, 2, 3, 5, 5, 7, 9]

前の質問: []
前S: []
並べ替え: []

前質問: [1]
前S: []
並べ替え: [1]

前の質問: []
前S: [1]
並べ替え: [1]
于 2013-03-19T01:07:46.153 に答える