Найти номер, ближайший ко всем числам в массиве

Question

Эта проблема в основном является проблемой оптимизации алгоритма.

У нас есть список, содержащий n элементов. например. {n1,n2,n3...nk} Этот список сортируется, и мы должны выяснить, число Ni, который

1. n1<=ni<=nk
2. Сумма расстояния ni от каждого номера минимальна.

Там может быть полным (nk-n1+1) возможных номеров, но наша цель состоит в том, чтобы узнать номер ni, который ближайших ко всем другим номерам.

Подход с грубой силой может быть переименован через n1 в nk и рассчитать сумму дистанций из всех номеров. Таким образом, мы можем легко найти число, которое ближе всего ко всем другим номерам в списке.

Но проблема с этим подходом заключается в том, что это не хорошо с точки зрения сложности времени. Сложность этого подхода составляет O(n^2).

Я думаю, что может быть лучший способ сделать это, что может решить эту проблему за меньшее время сложность.

Любой подход будет оценен.

Answer 1

Если по расстоянию вы имеете в виду distance(a,b) = abs(a-b), тогда вам просто нужно найти медианную.

Поиск медианы в отсортированном списке - O (1).

Answer 2

Найти среднее ... это занимает O (n). Затем пройдите по списку, чтобы найти ni для среднего (также принимает O (n)) ... на самом деле больше похоже на o (1/2n)

Answer 3

Ответ должен быть ROUND (SUM (n1, ..., nk)/k).