Я настраиваю новый сервер в Java-11 и хочу найти минимальное значение подгруппы из заданного отсортированного списка.
И я хотел бы знать, каков наиболее эффективный способ добиться этого.
Например:
sortedList = {1,2,3,4,5,6,7,8,9,10,11,12,13}
несортированная подгруппа = {13,6,3,12,2}
результат = 2.
Редактировать: sortedList - это сами значения
Важное примечание: отсортированный список будет относительно небольшим, приблизительно от 0 до 200 элементов.
Но это вычисление происходит для каждого пользователя, который присоединяется к серверу более одного раза, поэтому он должен быть оптимизирован.
Справочная информация о том, что я пробовал:
n = размер отсортированного списка
m = размер списка подгруппы
1) создал пустой список целых чисел sizeOf (m)
извлек все индексы из подгруппированных элементов из отсортированного списка.
в новый список O (m), выполнил минимальный поиск и нашел результат O (m-1).
Временная сложность = O (м) + O (м-1) ~ 2 * O (м)
Вопрос: это лучший подход?
2) извлек все индексы элементов подгруппы из отсортированного списка. вставил их в список sizeOf (n). [что означает список из n-m нулей + m целых чисел в нем].
O (1) для создания пустого списка sizeOf (n)
O (m) для извлечения всех индексов и вставки их в новый список,
пока, O (м) + O (1)
Теперь я знаю, что первое число, которое не равно нулю слева, является моим наименьшим индексом из моих отсортированных значений списка.
Вопрос: есть ли способ получить это первое число слева без итерации по n-м нулям?
примечание: на данный момент я подвергаю сомнению этот подход, поскольку теперь я вернулся к сложности n, m всегда будет намного меньше n.
всего, O (м) + O (1) + O (н-м) ~ O (м) + O (н-м) ~ O (н)
парсинг списка в строку и использование регулярных выражений намного дороже, чем вариант 1.
Показать код:
Я все еще нахожусь в стадии технического проектирования этой проблемы, поэтому я думаю, что приведенных выше примеров достаточно
Опишите ожидаемые и фактические результаты:
Мой ожидаемый результат в этой теме - найти самый быстрый способ получить результат минимального значения несортированного списка подгруппы из отсортированного списка.