Создайте структуру данных, которая поддерживает min, getLast, append, deleteLast в O (1), память ограничена n (не O (n)) + O (1)

Question

Мне нужно создать структуру данных, которая поддерживает следующее:

getMinElement, getLastElement, insertElement, deleteLastElement - в O(1) время выполнения.

Память ограничена n (не O (n)) i.e. Вы можете хранить не более n элементов в данный момент. плюс O (1) память.

(Важно: указатели также считаются 1, поэтому связанный список, например, не может быть и речи).

Пример:

insert(6) 
min() -> 6 
insert(10) 
insert(5) 
min() -> 5 
insert(7) 
delete() 
min() -> 5 
delete() 
min() -> 6 

Answer 1

Мы будем хранить самый последний минимум непосредственно. Это O (1) пространство.

Мы также будем использовать массив целых чисел, поскольку это, по-видимому, является нашей единственной опцией для пространства переменной длины. Но мы не будем хранить элементы напрямую. Вместо этого, когда мы вставляем элемент, мы сохраним разницу между этим элементом и (предшествующим) минимумом. Когда мы удаляем элемент, мы можем использовать эту разницу для восстановления предыдущего минимума, если это необходимо.

В Python:

class MinStorage: 

    def __init__(self): 
     self.offsets = [] 
     self.min = None 

    def insertElement(self, element): 
     offset = 0 if self.min is None else (element - self.min) 
     self.offsets.append(offset) 
     if self.min is None or offset < 0: 
      self.min = element 

    def getMinElement(self): 
     return self.min 

    def getLastElement(self): 
     offset = self.offsets[-1] 
     if offset < 0: 
      # Last element defined a new minimum, so offset is an offset 
      # from the prior minimum, not an offset from self.min. 
      return self.min 
     else: 
      return self.min + offset 

    def deleteLastElement(self): 
     offset = self.offsets[-1] 
     self.offsets.pop() 
     if len(self.offsets) == 0: 
      self.min = None 
     if offset < 0: 
      self.min -= offset 

Вот версия, которая позволяет любому беззнаковое 16-разрядное целое число в качестве элемента, а только хранит беззнаковые 16-битные целые числа в массиве:

class MinStorage: 

    Cap = 65536 

    def __init__(self): 
     self.offsets = [] 
     self.min = None 

    def insertElement(self, element): 
     assert 0 <= element < self.Cap 
     offset = 0 if self.min is None else (element - self.min) 
     if offset < 0: offset += self.Cap 
     self.offsets.append(offset) 
     if self.min is None or element < self.min: 
      self.min = element 

    def getMinElement(self): 
     return self.min 

    def getLastElement(self): 
     element = self.__getLastElementUnchecked() 
     if element < self.min: 
      # Last element defined a new minimum, so offset is an offset 
      # from the prior minimum, not an offset from self.min. 
      return self.min 
     else: 
      return element 

    def deleteLastElement(self): 
     element = self.__getLastElementUnchecked() 
     self.offsets.pop() 
     if len(self.offsets) == 0: 
      self.min = None 
     elif element < self.min: 
      # Popped element defined a new minimum. 
      self.min = element 

    def __getLastElementUnchecked(self): 
     offset = self.offsets[-1] 
     element = self.min + offset 
     if element >= self.Cap: 
      element -= self.Cap 
     return element 

Обратите внимание, что на языке с 16-разрядной арифметикой без знака, которая обертывается при переполнении/потоке, вам не понадобятся проверки и корректировки с использованием self.Cap. В C (§6.2.5/9) и C++ (§3.9.1/4) необязательная арифметика требуется вести себя по мере необходимости. Однако Python не поддерживает 16-разрядную арифметику без знака.

Answer 2

Используйте стек, который хранит как вставленное значение и текущую мин. Текущий min обновляется при вставке (push) значения, сравнивая значение с текущим min и при удалении (pop) значение, отображающее текущее значение min из верхней части стека.

Answer 3

Если вы можете предположить, что «данные находятся в диапазоне от 0 до 255 (int8)», и вам разрешено хранить целое число в два раза больше точности (int16), тогда вы можете сохранить «кумулятивный минимум» в верхний байт и точка данных в нижнем байте. Помимо этого, я не считаю, что это возможно в рамках ограничений, которые вы указали.