0
Заданный вопрос здесь. https://www.careercup.com/question?id=9406769, который запрашивает: Учитывая два несортированных массива int, найдите k-й элемент в объединенном отсортированном массиве. к элементу индекса, который начинается с 1.Большой (O) поиск элемента K в сборке MinHeap из 2 несортированных массивов
Что бы производительностью 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))
}
}
Где вы застряли? Знаете ли вы, что вы делаете большие операции? (добавить в очередь, dequue и т. д.)? –
Кстати, вам может понадобиться очередь с ограниченным приоритетом. См. Http://stackoverflow.com/questions/7878026/is-there-a-priorityqueue-implementation-with-fixed-capacity-and-custom-comparato –
Я думаю, что ответ должен быть O (n) для поиска времени куча. Теперь, когда я верю, что это должно включать построение кучи, слияние двух массивов в кучу, возможно, это n + O (log n). Где n должно быть конкатенацией массивов, а O (log n) - это вставка. Я прав? – Fabio