k番目に小さい番号

Question

サイズがA1、A2、...の並べ替えられた配列がn個あるとします。 （1 < = Ai < = 10^3）。 k番目の最小の整数をからユニークなの組み合わせにする必要があります。 O（A1 + A2 .. + An）未満の複雑さでこれを行う効率的な方法はありますか？

バイナリ検索と同様の方法で解決できますか？

PS：ここにはsimilar problemがありますが、ユニークな要素のために拡張する方法を理解できませんでした。

編集1：私はあなたの疑問を誤解していると思います。米国は、例えばてみましょう： N = 3、

A1 = 1、1、2、3

A2 = 6、7、9

A3 = 1、6、8

上記の配列のユニークな組み合わせは、{1,2,3,6,7,8,9}です。今度は2番目の要素が2を返し、4番目の要素が6を返すようにしたいとします。

Answer 1

はO(k n log n)可能である：

• 各アレイから最小の要素と最小ヒープを作成します。
• 繰り返しk回：
  • 分、ヒープ内の最小要素qを見て、最小qに等しくしながら、それを最小ヒープから
  • エキスを覚えています。抽出された各要素について
  • 、対応する配列からqよりも大きい最初の要素を置く
• 回答分ヒープ

Pythonコードの最小要素である：

import heapq 
import bisect 

def kth(A, k): 
    h = [] 

    for idx,a in enumerate(A): 
     if len(a) > 0: 
      heapq.heappush(h, (a[0], idx)) 

    for i in xrange(k): 
     if len(h) == 0: 
      return None 

     val, _ = h[0] 

     while (len(h) > 0) and (h[0][0] == val): 
      _, idx = heapq.heappop(h) 
      nxt = bisect.bisect_right(A[idx], val) 
      if nxt < len(A[idx]): 
       heapq.heappush(h, (A[idx][nxt], idx)) 

    if len(h) > 0: 
     return h[0][0] 
    return None 

Answer 2

空き領域がありますか、配列の数値は重複していますか？

そうでなければ、ユニークと非ユニークの2つのソートセットを作成できます。新しい番号はnonUniquesに存在する場合、

• 番号がユニークに存在する場合
• それをスキップし、削除します。 アレイの上に配列、あなたのループを追加し、2にその番号を追加するには、このようなセットをソートユニークからそれとその後すぐにソートされたユニークセットにk番目の最小の数を調べることができますユニーク

にNWW番号を追加それ以外の場合はnonUniques

に追加します。