2つのソートされていない配列からのMinHeapビルドでK要素を見つけるのが大きい（O）

Question

ここに質問を与えます。 https://www.careercup.com/question?id=9406769 which asks： 2つのソートされていないint配列がある場合、マージされソートされた配列のk番目の要素を探します。 1.

から始まるインデックスで k個の要素は何以下溶液のビーゴ性能であろう（プリントは1）：

object MergeTwoArraysFindK { 

    import scala.collection.mutable.PriorityQueue 

    def findK(arrayOne: Array[Int], arrayTwo: Array[Int], k: Int): Int = { 
    implicit val ord = Ordering[Int].reverse 
    val minHeap = new PriorityQueue[Int] ++= (arrayOne ++ arrayTwo).iterator 
    for (i <- 1 to k) 
     if (i == k) 
     return minHeap.dequeue() 
     else 
     minHeap.dequeue() 
    -1 
    } 

    def main(args: Array[String]): Unit = { 
    val arrayOne = Array[Int](3, 4, 9, 0, 1, 2, 4) 
    val arrayTwo = Array[Int](5, 4, 1, 0, 9, 8) 
    println(findK(arrayOne, arrayTwo, 4)) 
    } 
} 

Answer 1

はヒープを構築するためにO（N）時間がかかり、そしてO（n）余分なスペースが必要です。

k番目のアイテムを見つけることはO（k log n）です。minheap.dequeueを呼び出すたびにO（log n）が必要なので、kを呼び出しています。

この方法は、すべてをメモリに格納するのに十分なメモリがある場合に機能します。十分なメモリがない場合、2つの絶対的に巨大なファイルでこれをやっているとしたら、プロセスは少し異なります。 Time complexity of Kth smallest using Heapを参照してください。