Как найти k-й наибольший элемент в объединении двух отсортированных массивов?

Мне нужно найти самый большой элемент k в двух отсортированных массивах, но с твистом.

Этот алгоритм предполагает k<=max(m,n), и индексы идут наперекосяк, когда k>max(m,n). В моей проблеме я знаю, что всегда будет k>(m+n)/2 и, следовательно, k>min(m,n), поэтому мне нужно немного изменить Jules Olléon... я просто не вижу, какой бит: ~

Я нашел эту ссылку , но там есть ошибка (когда она реализована, она не возвращает правильный ответ)

Я знаю, что быстрым решением было бы умножить оба массива на -1 и взять k наименьшее из этого объединение и умножить ответ на -1, но это сделает код нечитаемым.

Хорошо, я думаю, что я пропустил ответ Нила или что-то еще, потому что это то, что я ему даю.

если вы не знакомы с самим собой: ошибка представляет собой индекс из связанной ошибки, вызванной getNth(v1,v2,k)

EDIT:

это очень незначительная модификация в простом и элегантном решении Дж. Ф. Себастьяна ниже - все ошибки мои, но, похоже, это работает. Цель состояла в том, чтобы работать с исходными индексами (т.е. Я не уверен, что идея Нейла незаменима).

Ответы

Ответ 1

Из ваших комментариев я понимаю, что вы хотите найти k-е наименьшее значение при заданном 2 отсортированном в обратной последовательности массиве, например, для a={5,4,3}, b={2,1,0}; и k=1 ожидаемый результат 0, т.е. минимальное значение - первое наименьшее значение (это означает, что k подсчитывается от 1).

Учитывая nsmallest() функцию, которая работает на отсортированных массивах и принимает пользовательский компаратор, вы можете:

#include <functional> // greater<>
#include <iostream>

#define SIZE(a) (sizeof(a) / sizeof(*a))

int main() {
  int a[] = {5,4,3};
  int b[] = {2,1,0};
  int k = 1; // find minimum value, the 1st smallest value in a,b

  int i = k - 1; // convert to zero-based indexing
  int v = nsmallest(a, a + SIZE(a), b, b + SIZE(b),
            SIZE(a)+SIZE(b)-1-i, std::greater<int>());
  std::cout << v << std::endl; // -> 0
  return v;
}

Я использовал @Neil предложение исправить индекс и @lambdapilgrim ответ для алгоритма:

#include <cassert>
#include <iterator>

template<class RandomIterator, class Compare>
typename std::iterator_traits<RandomIterator>::value_type
nsmallest(RandomIterator firsta, RandomIterator lasta,
          RandomIterator firstb, RandomIterator lastb,
          size_t n,
          Compare less) {
  assert(n < static_cast<size_t>((lasta - firsta) + (lastb - firstb)));
  if (firsta == lasta) return *(firstb + n);
  if (firstb == lastb) return *(firsta + n);

  size_t mida = (lasta - firsta) / 2;
  size_t midb = (lastb - firstb) / 2;
  if ((mida + midb) < n)
    return less(*(firstb + midb), *(firsta + mida)) ?
      nsmallest(firsta, lasta, firstb + midb + 1, lastb, n - (midb + 1), less) :
      nsmallest(firsta + mida + 1, lasta, firstb, lastb, n - (mida + 1), less);
  else
    return less(*(firstb + midb), *(firsta + mida)) ?
      nsmallest(firsta, firsta + mida, firstb, lastb, n, less) :
      nsmallest(firsta, lasta, firstb, firstb + midb, n, less);
}

Ответ 2

Самый большой элемент k th также является наименьшим элементом m + n + 1 - k th *, поэтому вы можете попытаться решить проблему таким образом.

* Подсчет с 1. Если k подсчитывается от 0, вместо этого используйте m + n - 1 - k.

Ответ 3

Я считаю, что вы хотите что-то аналогичное шагу слияния mergesort, где вы постепенно сравниваете i-й элемент m с j-м элементом n, но вместо того, чтобы сбрасывать значения в массиве, вы просто ищете kth наименьшее - поэтому, когда вы его найдете, верните это значение (и/или его индекс) и выйдите из функции.

Ответ 4

Я не уверен, что дело в k > max (m, n)!

Простое решение:

def find(v1, start1, end1, v2, start2, end2, k):
    i = (start1+end1)/2
    j = binsearchrank(v2, start2, end2, v1[i])
    ranki = (i-start1+1) + (j-start2)
    if ranki > k:
        return find(v2, start2, j, v1, start1, i, k)
    elif ranki < k:
        return find(v2, j, end2, v1, i+1, end1, k-ranki)
    else:
        return v1[i]

Сложность - это O (log ^ 2n)