Храните только три максимальных различных значения: при новом измерении добавьте его, удалите дубликаты и отбросьте всё ниже третьего места. Для фиксированного размера память и работа на измерение — O(1).
Реализуйте класс для микроконтроллера: метод сохраняет целочисленное значение датчика веса, второй метод возвращает три наибольших уникальных значения за всё время работы устройства по убыванию.
Храните только три максимальных различных значения: при новом измерении добавьте его, удалите дубликаты и отбросьте всё ниже третьего места. Для фиксированного размера память и работа на измерение — O(1).
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Храните только три максимальных различных значения: при новом измерении добавьте его, удалите дубликаты и отбросьте всё ниже третьего места. Для фиксированного размера память и работа на измерение — O(1).
Пример на Python для последовательных вызовов:
class WeightTop:
def __init__(self):
self._top = []
def add(self, value):
if type(value) is not int:
raise TypeError('integer required')
if value in self._top:
return
self._top.append(value)
self._top.sort(reverse=True)
del self._top[3:]
def top3(self):
return self._top[:]
До трёх уникальных измерений возвращаются все имеющиеся. Отрицательные значения допустимы. На микроконтроллере можно заменить список фиксированным массивом; вызовы из прерываний требуют согласованного доступа. Если «всё время» включает перезагрузки, нужно отдельно сохранять состояние в энергонезависимую память с учётом ресурса записи.