Sobes.tech
Junior
48

Papaskink, kaip sukonstruotas tavo pirmos užduoties sprendimas (unikalių elementų radimas išsaugant paskutinį įėjimą) ir kokia yra jo sudėtingumas.

Įmonės kur klausė
ИП Ганус Александр Андреевич

Atsakymas iš AI

sobes.tech AI

Для нахождения уникальных элементов с сохранением последнего вхождения можно пройтись по списку с конца к началу, сохраняя элементы во множество (Set) для отслеживания уже встреченных значений. При этом добавлять элементы в результат только если их ещё нет в множестве. После прохода нужно перевернуть результат, чтобы восстановить исходный порядок с последними вхождениями.

Пример на Dart:

List<T> uniqueLast<T>(List<T> list) {
  final seen = <T>{};
  final result = <T>[];
  for (var i = list.length - 1; i >= 0; i--) {
    if (!seen.contains(list[i])) {
      seen.add(list[i]);
      result.add(list[i]);
    }
  }
  return result.reversed.toList();
}

Сложность алгоритма — O(n), где n — длина списка, так как мы проходим по списку один раз и операции с множеством выполняются за амортизированное O(1).