SỐ SPECIAL Xét một dãy gồm N số nguyên A1, A2, A3, ... AN. Trong dãy số trên có 1 số chỉ xuất hiện đúng một lần (gọi là số special), và các số còn lại xuất hiện một số chẵn lần. Yêu cầu: Hãy tìm số special của một

2024-10-26 15:57:58

SỐ SPECIAL Xét một dãy gồm N số nguyên A1, A2, A3, ... AN. Trong dãy số trên có 1 số chỉ xuất hiện đúng một lần (gọi là số special), và các số còn lại xuất hiện một số chẵn lần. Yêu cầu: Hãy tìm số special của một dãy cho trước. Dữ liệu: Trong file văn bản SPECIAL.INP gồm: - Dòng đầu tiên là số N (N 107) - Dòng tiếp theo gồm N số nguyên, số thứ i là Ai với |Ai| 109. Kết quả: Ghi ra file văn bản SPECIAL.OUT gồm: Một dòng duy nhất là số cần tìm. Ví dụ: SPECIAL.INP 7 2 3 8 6 3 2 6 SPECIAL.OUT 8 ***Lập trình C++

Câu trả lời này dùng AI, hãy kiểm tra lại trước khi sử dụng

```cpp
#include
#include
#include
using namespace std;

int main() {
// Khai báo các biến cần thiết
ifstream fin("SPECIAL.INP");
ofstream fout("SPECIAL.OUT");

int N;
fin >> N; // Đọc số lượng phần tử N
unordered_map frequency; // Sử dụng unordered_map để đếm tần số xuất hiện của từng số

// Đọc dãy số và đếm tần số
for (int i = 0; i < N; i++) {
int num;
fin >> num;
frequency[num]++; // Tăng tần số của số này lên 1
}

// Tìm số special, tức là số xuất hiện một lần
for (const auto& pair : frequency) {
if (pair.second == 1) { // Nếu tần số bằng 1
fout << pair.first << endl; // Ghi số đó vào file
break; // Kết thúc sau khi tìm thấy số special
}
}

// Đóng các file
fin.close();
fout.close();

return 0;
}
```

Giải thích:
- Đầu tiên, chúng ta sử dụng `ifstream` để đọc dữ liệu từ file `SPECIAL.INP` và `ofstream` để ghi kết quả vào file `SPECIAL.OUT`.
- Số lượng phần tử được lưu vào biến `N` và chúng ta sử dụng `unordered_map` để đếm số lần xuất hiện của từng số.
- Trong vòng lặp, chúng ta đọc từng số và tăng tần số của nó trong `unordered_map`.
- Sau khi đã đếm xong tần số, chúng ta sử dụng vòng lặp để duyệt qua `unordered_map` và tìm số nào có tần số bằng 1, tức là số special.
- Khi tìm thấy số special đầu tiên, chúng ta ghi nó vào file và dừng vòng lặp.
- Cuối cùng, chúng ta đóng các file để hoàn tất chương trình.

Chương trình này có độ phức tạp thời gian là O(N), giúp xử lý hiệu quả ngay cả với N lên đến 10^7.

Đăng phản hồi