First Unique Number
2020/4/28
問題概要
[1, 1, 2, 3, 3, 4]みたいな配列が与えられるとして、最初にユニークな要素(だた1つしか存在しない要素)かつなるべく最初のものから取り出されるようなキューを実装せよ、という問題
この例でいうと2が最初に取り出され、該当しなければ-1を返す
解法
制約上、全ての関数の計算量をO(N)程度にしても一部テストケースでTLEとなった FirstUnique#addを呼び出した段階でqの先頭が必ずユニークになる状態に作った上で、FirstUnique#showFirstUnique呼び出し時は先頭を読むだけでokという形にした
code:solution.cpp
class FirstUnique {
public:
unordered_map<int, int> m;
queue<int> q;
FirstUnique(vector<int>& nums) {
for (int n : nums) map_value(n);
for (int n : nums) if (mn == 1) q.push(n); }
int showFirstUnique() {
if (q.size() > 0) return q.front();
return -1;
}
void add(int value) {
map_value(value);
if (mvalue == 1) q.push(value); // 重複した値はキューから削除
if (q.size() == 0) return;
int top = q.front();
q.pop();
if (q.size() == 0) return;
top = q.front();
}
}
void map_value(int value) {
if (m.count(value)) mvalue++; }
};
/**
* Your FirstUnique object will be instantiated and called as such:
* FirstUnique* obj = new FirstUnique(nums);
* int param_1 = obj->showFirstUnique();
* obj->add(value);
*/