Найдите k ближайших целых чисел для каждого элемента в массиве

Вашему алгоритму нужна небольшая корректировка, вот и все. У него нет поведения O(n²). Как есть, это по описанию O(max(k × n, n log n)), потому что, если я вас правильно понимаю, вы думаете, что выполняете O(k) сканирование вовне для каждого элемента, который не получает значимой выгоды от состояния окно, которое вы использовали для предыдущего элемента. Небольшая поправка уменьшит термин k × n до n, оставив его O(cost-of-sorting algorithm), например. O(n log n) для хороших сортировок общего назначения или несколько меньших больших O, больших или равных O(n) (для сортировок специального назначения, таких как сортировка подсчетом). И действительно, даже без этой настройки ваш существующий код уже вел бы себя так, просто вы его не видите (подстройка — это скорее то, как вы о ней думаете, где отсутствие настройки просто добавляет дополнительный шаг O(n), и переход от n к 2n не меняет большого O).

Ваша нижняя граница равна O(n log n), если вы используете сортировку общего назначения. Если входные данные попадают в ограниченные диапазоны, вы можете получить O(n + k) вычислительной работы с O(k) вспомогательной памятью, используя специальную сортировку, такую ​​как сортировка подсчетом, где k — размер диапазона, но мы предположим, что целые числа могут работать от -inf до inf, поэтому O(n + k) хуже, чем O(n log n) сортировка общего назначения. В любом случае, это нижняя граница, если остальная часть вашего алгоритма равна O(n) (и она должна быть как минимум такой же высокой, поскольку она должна обходить входной элемент за элементом), то ваш алгоритм сортировки определяет вашу общую работу.

Но то, как вы описываете это, звучит как поэлементная работа по регулировке окна O(k), на практике на самом деле выполняется n - k работа по сдвигу окна для целая последовательность с коэффициентом -k, распределенным по всей последовательности. Ваши вспомогательные указатели никогда сканируют назад, потому что каждый раз, когда вы продвигаетесь вперед, ваше старое значение оказывается ближе к новому значению, чем самое левое значение по определению. Таким образом, единственные возможности:

1. Окно предыдущего значения включало следующее значение; замените новое значение предыдущим значением, а затем проверьте: а. Если некоторое количество значений над старым окном ближе, чем значения в нижней части старого окна, окно перемещается вперед (до k раз), или б. Если значение над старым окном дальше, чем нижнее значение в окне, окно не смещается (кроме настройки для включения предыдущего значения вместо следующего значения)
2. Окно для предыдущего значения было полностью слева от него: безоговорочно замените нижнюю часть окна предыдущим значением (вместо замены нового значения предыдущим значением, как в № 1, поскольку нового значения не было в там), затем следуйте тем же правилам, что и в случае № 1 (либо окно остается неподвижным после свопа, либо оно сдвигается до k раз)

Таким образом, работа скольжения окна может достигать k на любом шаге (скажем, если k равно 2 и вы находитесь на значении 8 в [6, 7, 8, 100, 101, 102], то при переходе на 100, твоё предварительное окно из 6-7 безоговорочно становится 7-8, потом ты условно дважды сдвигаешься, сначала в 8-101, потом в 101-102, где и останавливается). Но поскольку единственными вариантами на любом данном шаге являются:

1. Окно не перемещается (фактически перемещается назад на единицу по отношению к позиции опережающего значения), или
2. Окно перемещается вверх до k + 1 вперед

это означает, что каждый раз, когда окно перемещается вперед на заданное количество шагов, s, оно вообще не должно двигаться для s предыдущих значений (чтобы переместить его назад достаточно, чтобы оно могло продвинуться вперед), что означает, что пиковая работа на элемент составляет O(k), но амортизированная работа на элемент составляет O(1) (и на самом деле она немного меньше единицы, потому что в ходе всего обхода вы перемещаться из окна, которое по определению является k элементами справа от текущего значения, на один элемент k влево, и эти «перемещения» влево фактически остаются на месте, так сказать, поэтому ваше окно слегка смещается меньше, чем один раз на элемент).

Ваш первоначальный план практически такой же, вы просто будете выполнять ненужную проверку на каждом этапе, чтобы увидеть, может ли окно двигаться назад (никогда не могло). Поскольку эта отдельная проверка имеет фиксированную стоимость, она составляет O(1) для каждого элемента, что не накладывает множителя на стоимость O(n) для обработки всей последовательности.

Вкратце: Ваш алгоритм уже оптимален по большому O в O(n) для работы, проделанной после сортировки. Если вы используете алгоритм сортировки общего назначения, работа O(n log n), которую он выполняет, доминирует над всем остальным; алгоритм специального назначения, такой как сортировка подсчетом, был бы единственным способом понизить ваш большой-0 всего процесса, включая сортировку, даже ниже, а минимальная стоимость была бы O(n), даже если бы у вас была волшебная «сортировка бесплатно» инструмент.