Сложность: medium
У вас есть очередь целых чисел, необходимо извлечь первый уникальный элемент из очереди.
Реализуйте класс FirstUnique:
- FirstUnique(int[] nums) Инициализирует объект числами в очереди.
- int showFirstUnique() возвращает значение первого уникального элемента в очереди и возвращает -1, если такого элемента нет.
- void add(int value) вставляет значение в очередь.
Пример:
Input:
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output:
[null,2,null,2,null,3,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5); // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2); // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3); // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1
👨💻 Алгоритм:
1⃣Инициализируйте объект FirstUnique с числами в очереди, добавляя их в структуру данных для отслеживания уникальности и порядка.
2⃣Метод showFirstUnique возвращает значение первого уникального элемента в очереди, если таковой существует, или -1, если уникальных элементов нет.
3⃣Метод add добавляет новое значение в очередь. Если значение уже было добавлено ранее, обновляет его статус уникальности и удаляет его из множества уникальных значений, если оно больше не уникально.
😎 Решение:
from collections import OrderedDict
class FirstUnique:
def __init__(self, nums: List[int]):
self.is_unique = {}
self.queue = OrderedDict()
for num in nums:
self.add(num)
def showFirstUnique(self) -> int:
for key in self.queue:
if self.is_unique[key]:
return key
return -1
def add(self, value: int) -> None:
if value not in self.is_unique:
self.is_unique[value] = True
self.queue[value] = None
elif self.is_unique[value]:
self.is_unique[value] = False
del self.queue[value]
Ставь 👍 и забирай 📚 Базу знаний