Editorial for Dấu chân lặp lại

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gợi ý 1 - Đếm từng giá trị

Ta cần biết mỗi giá trị xuất hiện bao nhiêu lần. Sau khi có tần suất, hãy chọn tần suất lớn nhất.

Gợi ý 2 - Xử lý trường hợp hòa

Nếu nhiều giá trị có cùng tần suất lớn nhất, đề yêu cầu chọn giá trị nhỏ nhất. Dùng map để duyệt các giá trị theo thứ tự tăng dần; khi gặp tần suất bằng kỷ lục hiện tại, không cần thay đáp án.

Lời giải đầy đủ

Ý tưởng

Duyệt mảng và lưu số lần xuất hiện của mỗi giá trị trong map<long long, int>. Map duyệt các khóa theo thứ tự tăng dần. Vì thế, chỉ cập nhật đáp án khi tìm được tần suất lớn hơn kỷ lục; nếu tần suất bằng nhau, giá trị nhỏ hơn đã được xét trước.

Độ phức tạp

Mỗi lần cập nhật map mất O(log N). Tổng thời gian O(N log N), bộ nhớ O(N).

Code C++17

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    map<long long, int> frequency;
    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        ++frequency[x];
    }

    long long answer = 0;
    int bestFrequency = 0;
    for (const auto& item : frequency) {
        long long value = item.first;
        int count = item.second;
        if (count > bestFrequency) {
            bestFrequency = count;
            answer = value;
        }
    }

    cout << answer << endl;
    return 0;
}