Cho dãy số nguyên a gồm N phần tử. Đếm xem có bao nhiêu cặp (i, j) trong đó i < j và a[i] = a[j]Input Specification
Dòng đầu là N số lượng phần tử của dãy. (0 < N <= 100000)
Dòng tiếp theo chứa n số nguyên là các phần tử của dãy số a (0< a.i <=1000)Output SpecificationSố cặp (i,j) thỏa mãn yêu cầu.
(Ngôn ngữ C++ nha)
Mình cần một tay giúp đây! Ai có thể đóng góp ý kiến để mình giải quyết câu hỏi này được không?
Các câu trả lời
Câu hỏi Tin học Lớp 9
Câu hỏi Lớp 9
Bạn muốn hỏi điều gì?
Đỗ Đăng Việt
Cách 1:```cpp#include#include using namespace std;int main() { int N; cin >> N; unordered_map countMap; for (int i = 0; i < N; i++) { int num; cin >> num; countMap[num]++; } int countPairs = 0; for (auto& pair : countMap) { int count = pair.second; countPairs += count * (count - 1) / 2; } cout << countPairs << endl; return 0;}```Cách 2:```cpp#include #include using namespace std;int main() { int N; cin >> N; vector arr(N); for (int i = 0; i < N; i++) { cin >> arr[i]; } int countPairs = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { if (arr[i] == arr[j]) { countPairs++; } } } cout << countPairs << endl; return 0;}```Câu trả lời cho câu hỏi: Để đếm số cặp (i, j) thỏa mãn điều kiện i < j và a[i] = a[j], ta có thể sử dụng cách 1 với cấu trúc dữ liệu unordered_map để đếm số lần xuất hiện của từng phần tử trong mảng. Sau đó, ta tính số cặp thỏa mãn bằng cách lấy tổng số cặp chính phương của số lần xuất hiện của từng phần tử. Hoặc ta cũng có thể sử dụng cách 2 với hai vòng lặp duyệt mảng để đếm số cặp thỏa mãn điều kiện trực tiếp.
Đỗ Bảo Hưng
Đảm bảo việc sử dụng map sẽ giúp giảm độ phức tạp của thuật toán xuống O(N) với N là số lượng phần tử của dãy số a.
Đỗ Hồng Vương
Cuối cùng, ta trả về số cặp đã tính được là kết quả của bài toán.
Phạm Đăng Phương
Sau đó, ta duyệt qua map để tính tổng số cặp (i, j) thỏa mãn yêu cầu. Với mỗi phần tử a[i], số cặp thỏa mãn sẽ là tổ hợp chập 2 của số lần xuất hiện của phần tử đó.
Phạm Đăng Dung
Đầu tiên, ta sử dụng một map để đếm số lần xuất hiện của từng phần tử trong dãy số a.