Найти пару через 2 массива с k-й наибольшей суммой

Учитывая два отсортированных массива чисел, мы хотим найти пару с k-й максимально возможной суммой. (Пара – это один элемент из первого массива и один элемент из второго массива). Например, с массивами

  • [2, 3, 5, 8, 13]
  • [4, 8, 12, 16]

Пары с наибольшими суммами

  • 13 + 16 = 29
  • 13 + 12 = 25
  • 8 + 16 = 24
  • 13 + 8 = 21
  • 8 + 12 = 20

Таким образом, пара с 4-й по величине суммой равна (13,8). Как найти пару с k-й максимально возможной суммой?

Я ищу решение, включающее минимальную кучу или максимальную кучу.

Это легко сделать в O(k*logk) . Я предполагаю, что массивы отсортированы в порядке убывания, чтобы упростить обозначение.

Идея проста. Мы найдем 1-й, 2-й, .., k-й максимальные значения один за другим. Но даже рассмотреть пару (i, j) нам нужно, чтобы оба (i-1, j) и (i, j-1) уже выбраны, потому что оба они больше или равны (i, j) .

Это похоже на то, что мы вставляем все n*m пар в кучу, а затем удаляем max k раз. Только нам не нужны все n*m пар.

 heap.add(pair(0, 0)); // biggest pair // remove max k-1 times for (int i = 0; i < k - 1; ++i) { // get max and remove it from the heap max = heap.popMax(); // add next candidates heap.add(pair(max.i + 1, max.j)); heap.add(pair(max.i, max.j + 1)); } // get k-th maximum element max = heap.popMax(); maxVal = a[max.i] + b[max.j]; 

Некоторые вещи, чтобы рассмотреть.

  • Дублированные пары могут быть добавлены в кучу, это можно предотвратить с помощью hashа.
  • Индексы должны быть проверены, например, max.i + 1 < a.length .

Я понимаю, что вы хотите кучу, но это не самое эффективное решение, как указывал phimuemue.

Вы можете max_heap оба массива и установить iterator в корне для обоих. На данный момент у вас самая большая сумма.

Теперь на каждом шаге найдите максимальный, невидимый узел среди детей и соседей обоих указателей – это следующая самая большая сумма. Переместите указатель в соответствующую кучу.

Повторите k раз.

Вот мой ответ, я думаю, что он работает хорошо, но может ли кто-нибудь сказать мне, в чем его сложность?

благодаря

 int ksum( int a[], int n, int b[], int m, int maxk ) { std::vector results; int* check = new int[m*n]; memset( check, 0, n*m*sizeof(int) ); int finali, finalj; int starti = 0, startj = 0; for( int k=1; kmaxj ) break; for( int j=i; jmaxi && j>=maxj ) break; if( check[i*m+j] == 0 ) { int tmp = a[i]+b[j]; if( tmp>max ) { max = tmp; finali = i, finalj = j; } maxi = i, maxj = j; break; } } } starti = finali; maxi=n, maxj=m; for( int j=startj; jmaxi ) break; for( int i=j; imaxj && i>=maxi ) break; if( check[i*m+j] == 0 ) { int tmp = a[i]+b[j]; if( tmp>max ) { max = tmp; finali = i, finalj = j; } maxi = i, maxj = j; break; } } } startj = finalj; if( max > 0 ) { check[finali*m+finalj] = 1; results.push_back( max ); } } delete[] check; if( maxk > results.size() ) return 0; else return results[maxk-1]; } int _tmain(int argc, _TCHAR* argv[]) { int a[] = {10,8,6,4,1}; int b[] = {9,6,3,2,1}; int res = ksum( a, 5, b, 5, 9 ); return 0; } 
  • Напишите программу, чтобы найти 100 самых больших чисел из массива из 1 миллиарда чисел
  • Выполнение qsort vs std :: sort?
  • Сортировка одной строки в Java
  • Порядок Mysql по определенным значениям идентификатора
  • Использование bash для сортировки данных по горизонтали
  • Сортировка списка пользовательских classов
  • Как отсортировать ArrayList, используя несколько критериев сортировки?
  • Какова цель фаз перетасовки и сортировки в редукторе в Программе сокращения карты?
  • Закажите «смешанный» вектор (цифры с буквами)
  • Сортировка текстового файла по длине строки, включая пробелы
  • Как использовать std :: sort для сортировки массива в C ++
  • Давайте будем гением компьютера.