Số duy nhất đầu tiên trong C ++

Giả sử chúng ta có một hàng đợi các số nguyên, chúng ta cần truy xuất số nguyên duy nhất đầu tiên trong hàng đợi đó. Chúng ta phải triển khai lớp được gọi là FirstUnique:Nó sẽ được khởi tạo bởi các số trong hàng đợi. Xác định một hàm showFirstUnique (), hàm này sẽ trả về giá trị của số nguyên duy nhất đầu tiên của hàng đợi và trả về -1 nếu không có số nguyên nào như vậy. Một phương thức khác là add (value), nó sẽ chèn giá trị vào hàng đợi.

Vì vậy, nếu đầu vào giống như

• Khởi tạo bằng [2,3,4] rồi gọi các hàm như sau -

• showFirstUnique ()

• thêm (5)

• showFirstUnique ()

• thêm (2)

• showFirstUnique ()

• thêm (3)

• showFirstUnique (),

thì đầu ra sẽ lần lượt là 2, 2, 3, -1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàng đợi q

• Xác định một bản đồ cnt

• Trình khởi tạo sẽ lấy mảng

  • cho mỗi phần tử tôi trong nums

    • (tăng cnt [i] lên 1)

  • cho mỗi phần tử tôi trong nums

    • nếu cnt [i] giống 1, thì -

      • chèn tôi vào q

• Xác định một hàm showFirstUnique ()

• while (không phải q trống và cnt [phần tử đầu tiên của q]> 1), do -

  • xóa phần tử khỏi q

• return (nếu q trống thì -1, còn lại là phần tử đầu tiên của q)

• Xác định một hàm add (), hàm này sẽ có giá trị,

• (tăng cnt [value] lên 1)

• nếu cnt [value] giống với 1, thì -

  • chèn giá trị vào q

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

{2,3,5}
ob.showFirstUnique();
ob.add(5);
ob.showFirstUnique();
ob.add(2);
ob.showFirstUnique();
ob.add(3);
ob.showFirstUnique();

Đầu ra

2
2
3
-1