← 返回题目列表

AtCoder · APG4b_bz

EX23. 第3.03节

中文机器翻译题面 查看原题
page_url:https://atcoder.jp/contests/apg4b/tasks/APG4b_bz

返回说明页面

問題文

N元素数组 给出了A_1, A_2, \ldots, A_N。 在这个数组的值中,找到出现次数最多的值以及出现的次数。

然而,假设不存在出现次数最多的多重值。

由于限制较大,因此创建程序时请注意计算量。


制約

  • 0 \leq N \leq 10^5
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 不存在出现次数最多的多重值。

入力

输入是从标准输入按以下格式给出的:

N
A_1 A_2 \ldots A_N

出力

値 出現回数

请输出最常出现的值以及出现的次数,以空格分隔。


Judge 还测试除以下输入示例之外的案例。注意。

特别是,判断测试用例包含大量输入,因此请小心不要导致 TLE。

入力例1

5
1 4 4 2 3

出力例1

4 2

输入数组中包含的每个值的出现次数如下。

  • 1 出现一次
  • 2 出现一次
  • 3 出现一次
  • 4 出现两次

最大出现次数为 2,其值为 4,因此将输出“4 2”。

入力例2

6
3 2 3 1 3 2

出力例2

3 3

入力例3

1
1000000000

出力例3

1000000000 1

提示

点击打开提示

  • “值→出现次数”之间的关系 使用map进行管理。 向
  • map添加和访问值的计算复杂度为O(\log N)。
  • 在这个问题中 有了计算量N^2是10^{10}所以,O(N^2),就变成了TLE。
  • N \log N约为。 所需的计算量为1.6*10^6所以,O(N \log N)。


测试输入/输出

只有当你写的程序没有变成AC并且你找不到原因时,请看这个。

单击查看测试输入/输出

测试输入 1

因数据太大而省略

测试输入 2

因数据太大而省略


解答例

观看前请务必亲自尝试一下问题。

点击查看示例答案

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }

  map<int, int> cnt;
  for (int x : A) {
    if (cnt.count(x)) {
      // 既に含まれているならインクリメント
      cnt.at(x)++;
    } else {
      // 含まれていないなら、1を追加
      cnt[x] = 1;
    }
  }

  int max_cnt = 0;  // 出現回数の最大値を保持
  int ans = -1;     // 出現回数が最大になる値を保持
  for (int x : A) {
    // 今見ているxの出現回数が、その時点の最大よりも大きければ更新
    if (max_cnt < cnt.at(x)) {
      max_cnt = cnt.at(x);
      ans = x;
    }
  }

  cout << ans << " " << max_cnt << endl;
}