Знайти k-тий по порядку елемент у двох відсортованих масивах

Задача

Написати функцію яка приймає два відсортовані масиви цілих чисел з унікальними значеннями і знайти k-тий по порядку елемент.

Зробити це треба швидше ніж за лінійний час.

Рішення

Якщо просто мати по індексу на масив і пересувати їх на найменший елемент то усього нам знадобиться k ітерацій.

Так само якщо ми спробуємо злити масиви то не вдасться зробити це швидше ніж за лінійнипй час.

Якщо ж скористатися бінарним пошуком то загальна складність становитиме O(lg M + lg N), де M та N розміри вхідних масивів.

Робимо ми це так:

  1. будуємо індекси i та j такі що i + j == k – 1. Наприклад ділимо відрізки навпіл.
  2. якщо B[j-1] < A[i] < B[j] то A[j] є результатом пошуку
  3. якщо A[i-1] < B[j] < A[i] то результатом буде B[j]
  4. модифікуємо індекси таким чином:
    1. якщо A[i] < B[j] то:
      1. якщо B[j] є останнім елементом у масиві то значення яке ми шукаємо знаходиться в A
      2. інакше пересуваємо j на половину масиву вліво, і рівно на стільки ж позицій пересуваємо i (для того щоб їх сума дорівнювала k)
    2. Робимо схожі перевірки:
      1. якщо A[i] є останнім елементом у масиві то значення яке ми шукаємо знаходиться в B
      2. інакше пересуваємо i на половину масиву вліво, і рівно на стільки ж позицій пересуваємо j
  5. повертаємося до кроку 2.

Код на gist:

Залишити відповідь

Зайти з допомогою: