Số cặp

Xem PDF
Tác giả:
admin
Dạng bài
Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một mảng gồm \(n\) số nguyên dương \(a_1,\) \(a_2,\) \(a_3,\) \(...,\) \(a_n.\)

Yêu cầu : Hỏi có bao nhiêu cặp số bằng nhau ? \((\)Bao nhiêu cặp \(a_i\) \(=\) \(a_j\) với \(i\) \(\neq\) \(j,\) \((ai,\) \(aj)\) và \((aj,\) \(ai)\) chỉ được tính là \(1\) cặp\().\)

Input

  • Dòng thứ nhất là chiều dài \(n\) của mảng \((1\) \(\leq\) \(n\) \(\leq\) \(10^5).\)
  • Dòng thứ hai gồm \(n\) số nguyên \(a_1,\) \(a_2,\) \(a_3,\) \(...,\) \(a_n\) \((1\) \(\leq\) \(a_i\) \(\leq\) \(10^5),\) mỗi số cách nhau một khoảng trắng.

Output

  • Là số nguyên xác định số lượng các cặp bằng nhau.

Example

Test 1

Input 
5
8 2 9 8 1
Output 
1

Test 2

Input 
7
6 2 4 2 4 3 4
Output 
4

Bình luận


  • 0
    nob_Python69    9:50 a.m. 11 Tháng 5, 2024

    code Python O(n) đơn giản ko dùng đệ quy:
    from collections import Counter
    n = int(input())
    a = list(map(int, input().split()))
    cnt = Counter(a)
    ans = 0
    for i in cnt.values():
    ans += (i-1)*i//2
    print(ans)


    • 0
      thuannguyen1972dn    7:14 p.m. 2 Tháng 5, 2024

      code python:def chap(k, n):
      if k == 0 or k == n:
      return 1
      elif k == 1:
      return n
      else:
      return chap(k - 1, n - 1) + chap(k, n - 1)

      def main():
      import sys
      input = sys.stdin.read
      data = input().split()

      n = int(data[0])  # Đọc giá trị của n
a = list(map(int, data[1:n+1]))  # Đọc dãy a

# Sử dụng dictionary để đếm số lần xuất hiện của từng phần tử trong a
mp = {}
for num in a:
    if num in mp:
        mp[num] += 1
    else:
        mp[num] = 1

ans = 0
# Duyệt qua từng cặp (key, value) trong dictionary mp
for key, value in mp.items():
    if value == 2:
        ans += 1
    elif value > 2:
        ans += chap(2, value)

print(ans)

      if name == "main":
      main()


      • 0
        khaidadao    11:10 p.m. 10 Tháng 4, 2024

        Để tối ưu hóa bài này thì nên sài đệ quy về : chập (2, số lượng phần tử) ; )
        Code mẫu ac : https://www.ideone.com/gngGZL


        • 32
          SPyofgame    6:26 p.m. 5 Tháng 6, 2020

          Spoiler Alert

          Hint

          Gọi M[x] = số lần xuất hiện của x trong mảng a

          Kết quả bài toán là res = Σ(x ∈ a){ M[x] * (M[x] - 1) / 2 }

          1 phản hồi