1. Đề bài
Cho một mảng số nguyên n phần tử.Hãy đếm trong mảng có bao nhiêu cặp số giống nhau.(Mỗi số nguyên chỉ được bắt cặp duy nhất một lần).
Khoảng giá trị của n : từ 2 đến 10^6.
Sample Input:
|
1 2 3 |
9 10 20 20 10 10 30 50 10 20 |
Sample Output:
|
1 2 |
3 |
Miêu tả đề bằng hình ảnh:
2. Hướng giải.
Với việc phải nối các cặp số với nhau các số nào đã nối lại rồi không xét nữa. Như vậy ta phải có một mảng để lưu giữa trạng thái.
Duyệt từng phần tử trong mảng với các phần tử còn lại . Nếu thỏa điều kiện bằng nhau và trang thái của chúng chưa được bắt cặp thì
tiến hành bắt cặp.Tiếp tục với số tiếp theo.
3.Code.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
static int sockMerchant(int n, int[] ar) { if (n <= 0) return 0; boolean[] status = new boolean[n]; int count = 0; for (int i = 0 ; i < n ; i++) { for (int j = i; j < n ; j++) { if (ar[i] == ar[j] && status[i] == false && status[j] == false && i != j) { status[i] = true; status[j] = true; count++; break; } } } return count; } |