Какой алгоритм используется для поиска n-го сортированного подмассива неупорядоченного массива?

Недавно у меня был этот вопрос в интервью, и я потерпел неудачу и теперь ищу ответ.

  • Скажем, у меня есть большой массив из n целых чисел, все разные.

  • Если этот массив был заказан, я мог бы разделить его на x меньше массивы, все размеры y, за исключением, может быть, последнего, что может быть меньше. Я мог бы извлечь n-й подмассив и вернуть его, уже отсортированный.

Пример: Array 4 2 5 1 6 3. Если y = 2 и мне нужен второй массив, это будет 3 4.

Теперь я просто сортировал массив и возвращал n-й подмассив, который принимает O (n log n). Но мне сказали, что существует способ сделать это в O(n + y log y). Я искал в Интернете и ничего не нашел. Идеи?

Ответы

Ответ 1

Алгоритм, который вы ищете, это Алгоритм выбора, который позволяет находить статистику k-го порядка в линейном времени. Алгоритм довольно сложный, но стандартная библиотека С++ удобно предоставляет его реализацию.

Алгоритм поиска k-го сортированного интервала, который имел в виду у интервьюеров, был следующим:

  • Найти b=(k-1)*y -ый порядок статистики в O (N)
  • Найти e=k*y -ный порядок статистики в O (N)
  • Между b и e будет число y. Храните их в отдельном массиве размером y. Эта операция принимает O (N)
  • Сортировка массива размера y для O (y * log 2 y).

Общая стоимость O (N + N + N + y * log 2 y), то есть O (N + y * log 2 y)

Ответ 2

Вы можете комбинировать std::nth_element и std::sort для этого:

std::vector<int> vec = muchData();
// Fix those bound iterators as needed
auto lower = vec.begin() + k*y;
auto upper = lower + y;

// put right element at lower and partition vector by it
std::nth_element(vec.begin(), lower, vec.end());
// Same for upper, but don't mess up lower
std::nth_element(lower + 1, upper - 1, vec.end());
// Now sort the subarray
std::sort(lower, upper);

[lower, upper) теперь является k-м сортированным подмассивом длины y с требуемой сложностью в среднем.

Проверять для особых случаев, таких как y = 1, перед использованием в реальном мире, но это общая идея.