@JuniorNoobie
Сижу в поддержке, пишу мелкие проекты

Как вернуть первые N максимальных элементов из массива без сортировки массива?

Доброе утро!
Возник вопрос как решить следующую задачу.
Есть массив с объектами. После некоей операции к каждому объекту из массива прибавляется новое поле distance, в котором лежит целое число. Необходимо вернуть первые N элементов из массива, упорядоченного по возрастанию поля distance.

Решение в лоб:
const arr = [{id:1, name: "object1"}, {id:1, name: "object1"}, ...];
const n = 5;
let resultArr = arr.map(obj => Object.assign({}, obj, {distance : setDistance(obj)}));
resultArr = resultArr.sort((a,b) => b.distance - a.distance);
console.log(resultArr.slice(0, n));


Меня смущает, что при очень большом количестве элементов в массиве я буду терять много времени на сортировке, хотя мне нужны буквально первые N элементов (т.е. хвост массива можно и не упорядочивать).
  • Вопрос задан
  • 180 просмотров
Пригласить эксперта
Ответы на вопрос 5
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Есть такой алгоритм. Называется quickSelect. Фактически, это обрезанный quickSort, где после выбора ведущего элемента и разбивки массива работа продолжается только в той половине, где находится раздел между первыми K элементами и остальными N-K.

Пусть у вас N элементов в массиве и надо вернуть K минимальных. Тогда сортировка будет работать за O(N log N), а quickselect за O(N) в среднем*. В худшем случае может быть и квадратичное время работы, но этот случай практически невозможен, если реализация испольует случайные числа для выбора ведущего элемента.

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

Суть его в том, чтобы в куче (heap aka priority queue) поддерживать пока найденные K минимальных элементов. При этом куча будет на максимум. Сначала туда кладутся первые k элементов массива, а потом каждый следующий вытесняет максимальный элемент в куче, если он его меньше.

* Вообще говоря, можно заставить quickselect и quicksort работать идеально всегда, если использовать алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна, который ищет медиану за O(n). Но на практике этот алгоритм не применятеся, потому что у него такая константа, что там на логарифм хватит и еще на квадрат останется.
Ответ написан
@res2001
Developer, ex-admin
Вместо сортировки можно использовать алгоритм выборки k-той статистики (quik select).
Алгоритм не полностью сортирует массив, а только те элементы, которые необходимо для получения k-ой статистики. Для вашей задачи алгоритм надо вызывать N раз (с параметром от 1 до N).
Чтоб не портить оригинальный массив можно сделать копию, содержащую ссылки на элементы оригинального массива и вызывать алгоритм на копии.

Если N относительно не большое и массив не велик, то можно просто искать максимум N раз. При нахождении очередного максимума заменять значение элемента на минимально возможное и сохранять ссылку на измененный элемент. После нахождения всех N максимумов - восстанавливать значения в массиве.
Ответ написан
dollar
@dollar
Делай добро и бросай его в воду.
Строго - никак.

Есть разные алгоритмы частичной сортировки с минимальной сложность O(N+KlogN), где K - количество максимумов, а N - размер массива, но совсем без сортировки не получится в общем случае.

Если не строго, то сильно зависит от специфики задачи, из которой нужно взять какие-то доп. условия и допущения. Именно они позволят оптимизировать алгоритм.

Например, если K не строгое, а лишь примерное, то можно прикинуть некий порог, выше которого эти элементы будут расположены. Скажем, K=10, N=1000 элементов, и в каждом случайное число от 1 до 1000. Тогда можно почти уверенно заявить, что все искомые элементы больше 970. Пробегаем массив один раз и находим все элементы больше 970. Их окажется около 30 плюс-минус. Главное, что не менее 10. Далее этот маленький массив можно отсортировать, но это снова сортировка.
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
const littleN = (arr, N) => arr.reduce(
  (acc, cur) => {
    const idx = acc.findIndex((el) => el.distance > cur.distance);
    if (idx !== -1) {
      acc.pop();
      acc.splice(idx, 0, cur);
    }
    return acc;
  },
  Array(N).fill(arr[0])
);

Но не уверен, что такая функция будет быстрее штатной сортировки, особенно при небольших массивах.
Ответ написан
@Akina
Сетевой и системный админ, SQL-программист.
Да собсно создаёшь итоговый массив размером N и перебираешь элементы исходного массива, помещая их в итоговый массив с поддержанием сортированности последнего. Соответственно первые N элементов исходного просто помещаются туда с сортировкой, а все последующие либо не помещаются, если они меньше наименьшего, либо помещаются в правильное место, чтобы сохранялась сортированность, выдавливая при этом наименьший из элементов. По завершении перебора в итоговом массиве находится требуемое число максимальных элементов.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы