Số lần xuất hiện

View as PDF



Author:
Problem types
Points: 100 (p) Time limit: 1.0s Memory limit: 650M Input: stdin Output: stdout

Cho một dãy gồm \(n\) số nguyên dương \(A_1,A_2,\ldots,A_n\).

Yêu cầu: Hãy in ra tất cả các số trong mảng \(A\) cùng với số lần xuất hiện của chúng.

Input

  • Dòng đầu chứa số \(n\) (\(n\leq 10^5\)).
  • Dòng thứ hai chứa \(n\) số nguyên dương \(A_1,A_2,\ldots,A_n\) (\(A_i\leq 10^6\)).

Output

  • Gồm \(n\) dòng, mỗi dòng ghi số hạng thứ \(A_i\) và số lần xuất hiện của chúng.

Example

Test 1

Input
9
2 3 1 2 3 4 5 4 3
Output
2 2
3 3
1 1
2 2
3 3
4 2
5 1
4 2
3 3

Comments


  • -2
    minhtuanitk20    10:21 a.m. 12 sep, 2021

    map là ok ac nhe mn

    1 reply

    • 29
      N7hoatt    5:28 p.m. 4 aug, 2020 edit 3

      HINT


      Ý TƯỞNG 1: CÀY TRÂU

      • ta cho duyệt qua từng phần tử của mảng xét với phần tử đang đứng hiện tại, nếu bằng nhau ta tăng biến dem++

      Reference TLE CODE | \(O(n^2)\) time | Brute-forces

       int main()
       {
            cin>>n;
            for(int i=1; i<=n; i++)
               cin>>a[i];
            for(int i=1; i<=n; i++)
            {
                 ll dem=0;
                 for(int j=1; j<=n; j++)
                      if(a[i]==a[j])
                          dem++;
                 cout<<a[i]<<" "<<dem<<endl;
            }
       }
      

      Ý TƯỞNG 2: ĐẾM PHÂN PHỐI

      • ta tạo ra một mảng \(dem[]\) nhằm lưu lại tần số của các phần tử trong mảng bằng cách duyệt qua từng phần tử và tăng giá trị của dem[a[i]]++

      Reference AC CODE | O(n) time | Distrubition-count

       int main()
       {
           cin>>n;
           for(int i=1; i<=n; i++)
               cin>>a[i], dem[a[i]]++;
           for(int i=1; i<=n; i++)
               cout<<a[i]<<" "<<dem[a[i]]<<endl;
       }
      

      p/s:upvote hoặc không tôi sẽ gửi đồng chí tới gulag

      6 replies