pro.algorithms
Здравствуйте. Мне надо найти Kth Smallest Sum of Two Sorted
Arrays за O(k log k).
Например, если A = {1, 2, 3}, а B = {2, 3, 4}, то
A + B = {3, 4, 5, 4, 5, 6, 5, 6, 7}, тогда для k = 3 (k от 0} ответ будет 5.
https://stackoverflow.com/questions/5212037/find-the-pair-across-2-arrays-with-kth-largest-sum
Нашел такое решение для LargestSum, правда ли что решение корректно и работает за O(k log k)? И если в решении для LargestSum MaxHeap заменить на MinHeap, то будет решение моей задачи?
9 ответов
Я может тупой (скорее всего), но если я правильно понял задачу, то у тебя два массива по возрастанию отсортированы.
Степан
Автор вопроса
Я может тупой (скорее всего), но если я правильно ...
Ну да. Забыл указать
Ну да. Забыл указать
Т.е. их первые элементы всегда наименьшие числа в данном массиве чисел?
Степан
Автор вопроса
Ну да.
А тебе нужно найти найменьшую сумму a[i] + b[j] ?
Степан
Автор вопроса
А тебе нужно найти найменьшую сумму a[i] + b[j] ?
k-ую наименьшую сумму
Можно решить без доп памяти. За те же O(klogk)
Или minHeap. При доставании элемента (i, j). Если i=max(i, j), то push (i+1,j). Если j=max(i, j), то push (i, j+1).
Степан
Автор вопроса
Или minHeap. При доставании элемента (i, j). Если ...
Почему алгоритм коррректен?
Похожие вопросы
Обсуждают сегодня