Phần tử áp đảo


Submit solution

Points: 4 (partial)
Time limit: 1.0s
Memory limit: 977M

Author:
Problem type

Cho dãy số nguyên \(a_1, a_2 ,..., a_N\) có \(N\) phần tử, bạn hãy tìm phần tử áp đảo là phần tử có tần suất xuất hiện nhiều hơn \(\frac{N}{2}\)

Input

Dòng đầu là số phần tử N \((1 < N \le 10^6)\)

Dòng tiếp theo là \(N\) số nguyên mỗi số có giá trị tuyệt đối không vượt quá \(10^9\)

Output

Một số nguyên duy nhất là giá trị của phần tử áp đáo, nếu dãy không có phần tử áp đảo in ra thông báo "khong co phan tu ap dao"

Example 1

Input

8
1 9 0 0 1 5 0 0

Output

khong co phan tu ap dao

Example 2

Input

9
-3 4 -5 4 6 4 4 1 4

Output

4
tichpx

Comments


  • 2
    QuynhSon_CNTT4_K62  commented on Sept. 11, 2022, 10:31 a.m.

    Thì ra bài này không cần map hay sort vẫn làm được

    Boyer–Moore majority vote algorithm

    Độ phức tạp thời gian: O(n)


    • 1
      Hoan_CNTT_VA2_K61  commented on Sept. 13, 2022, 2:52 a.m.

      very helpful !!

      • mặc dù unordered_map cũng cho độ phức tạp thời gian là O(n), nhưng độ phức tạp không gian là O(n) nên xử lý số lớn sẽ chậm hơn 1 chút so với "Boyer–Moore majority vote algorithm"

    • 2
      TICHPX  commented on Sept. 12, 2022, 3:43 a.m. edited

      Mình nghĩ nếu phần tử đó có thì nó chính là trung vị do đó

      Bước 1. Tìm trung vị bằng thuật toán tìm phần tử thứ k (gần giống như Quicksort)

      Bước 2. Đếm số phần tử đó nếu đúng là hơn n/2 là được


      • 1
        QuynhSon_CNTT4_K62  commented on Sept. 13, 2022, 12:51 a.m.

        nếu thế nó lại về O(nlogn) rồi thầy (Quicksort/2)


        • 2
          TICHPX  commented on Sept. 13, 2022, 3:17 a.m.

          Tìm trung vị là tìm phần tử thứ k (có độ phức tạp O(n))


  • 1
    LãoTam  commented on Oct. 21, 2021, 9:27 a.m.

    [user:^_^]Tham Khảo

    #include<bits/stdc++.h>
    #include<iostream>
    using namespace std;
    
    int main()
    {
        long n;
        long long x;
     map<long long, long> M;
        scanf("%ld",&n);
        for(long i=1;i<=n;i++)
        {
            scanf("%lld",&x);
            M[x]++;
        }
        n/=2;
        for(auto p:M)
        {
            if(p.second>n) {printf("%lld",p.first);return 0;}
        }
        printf("khong co phan tu ap dao");
    }

  • 1
    SANG_CNTT1_K61  commented on Oct. 8, 2021, 11:04 a.m. edit 2
    #include"bits/stdc++.h"
    using namespace std;
    using ll = long long;
    int main()
    {
         ios_base::sync_with_stdio(0); 
        cin.tie(0); 
    int n;
    cin>>n;
    map< long long, int> mp;
    for(int i=0;i<n;i++){
        ll x;cin>>x;
        mp[x]++;
    }
    ll res=INT_MIN,pun;
    for(auto it :  mp){
       if(it.second>res){
        res=it.second;
        pun=it.first;
       }
    }
    if(res>n/2){
        cout<<pun;
    }else cout<<"khong co phan tu ap dao";
    
    return 0;
    }

  • 1
    TICHPX  commented on Aug. 20, 2020, 10:47 p.m.

    Bạn hãy dùng fast io để nhập xuất dữ liệu bằng cin, cout mới tránh được lỗi TLE