从 2 个未排序的数组中找到 MinHeap 构建中的 K 元素的 Big(O)

Question

在这里给出问题。 https://www.careercup.com/question?id=9406769 询问：给定两个未排序的 int 数组，在合并后的排序数组中找到第 k 个元素。索引中从 1 开始的第 k 个元素。

以下解决方案的 BigO 性能如何（打印 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)space.

找到第 k 个项目是 O(k log n) 每次调用 minheap.dequeue 都需要 O(log n)，而您正在进行 k 次调用。

如果您有足够的内存将所有内容保存在内存中，则此方法有效。如果您没有足够的内存，假设您正在处理两个绝对巨大的文件，那么过程会略有不同。参见 Time complexity of Kth smallest using Heap。

从 2 个未排序的数组中找到 MinHeap 构建中的 K 元素的 Big(O)

Big(O) of finding K element in a MinHeap build from 2 unsorted arrays

big-o

scala

priority-queue