정수 대기열이 있다고 가정하고 해당 대기열에서 첫 번째 고유 정수를 검색해야 합니다. FirstUnique라는 클래스를 구현해야 합니다. 이 클래스는 대기열의 숫자로 초기화됩니다. 하나의 함수 showFirstUnique()를 정의하면 대기열의 첫 번째 고유 정수 값을 반환하고 해당 정수가 없으면 -1을 반환합니다. 또 다른 방법은 add(value)입니다. 이것은 큐에 값을 삽입합니다.
따라서 입력이 다음과 같으면
-
[2,3,4]로 초기화한 다음 다음과 같이 함수를 호출합니다. -
-
showFirstUnique()
-
추가(5)
-
showFirstUnique()
-
추가(2)
-
showFirstUnique()
-
추가(3)
-
showFirstUnique(),
그러면 출력은 각각 2, 2, 3, -1이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 대기열 정의 q
-
하나의 맵 cnt 정의
-
이니셜라이저는 배열을 사용합니다.
-
숫자의 각 요소 i에 대해
-
(cnt[i]를 1씩 증가)
-
-
숫자의 각 요소 i에 대해
-
cnt[i]가 1과 같으면 -
-
i를 q에 삽입
-
-
-
-
showFirstUnique()
함수 정의 -
동안(q가 비어 있지 않고 cnt[q의 첫 번째 요소]> 1), 다음을 수행합니다. -
-
q에서 요소 삭제
-
-
반환(q가 비어 있으면 -1, 그렇지 않으면 q의 첫 번째 요소)
-
add() 함수를 정의하면 가치가 있습니다.
-
(cnt[값]을 1씩 증가)
-
cnt[값]이 1과 같으면 -
-
q에 값 삽입
-
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class FirstUnique {
public:
queue <int> q;
map <int, int> cnt;
FirstUnique(vector<int>& nums) {
for (int i : nums) {
cnt[i]++;
}
for (int i : nums) {
if (cnt[i] == 1) {
q.push(i);
}
}
}
int showFirstUnique() {
while (!q.empty() && cnt[q.front()] > 1) q.pop();
return q.empty() ? -1 : q.front();
}
void add(int value) {
cnt[value]++;
if (cnt[value] == 1)
q.push(value);
}
};
main(){
vector<int> v = {2,3,5};
FirstUnique ob(v);
cout << (ob.showFirstUnique()) << endl;
ob.add(5);
cout << (ob.showFirstUnique()) << endl;
ob.add(2);
cout << (ob.showFirstUnique()) << endl;
ob.add(3);
cout << (ob.showFirstUnique()) << endl;
} 입력
{2,3,5}
ob.showFirstUnique();
ob.add(5);
ob.showFirstUnique();
ob.add(2);
ob.showFirstUnique();
ob.add(3);
ob.showFirstUnique(); 출력
2 2 3 -1