EX20 - 最頻値 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

説明ページに戻る

問題文

N要素の配列 A₁, A₂, …, Aₙ が与えられます。
この配列の中の値のうち、出現回数が最も多い値とその出現回数を求めてください。

ただし、出現回数が最大になる値は複数存在しないものとします。

制約が大きいため計算量に注意してプログラムを作成してください。

制約

  • 0 ≤ N ≤ 10⁵
  • 0 ≤ Aᵢ ≤ 10⁹ (1 ≤ i ≤ N)
  • 出現回数が最大になるような値は複数存在しない

入力

入力は次の形式で標準入力から与えられます：

N
A₁ A₂ … Aₙ

出力

値 出現回数

出現回数が最も多い値と、その出現回数をスペース区切りで出力してください。

  • ジャッジでは入力例以外のケースに関してもテストされることに注意してください。
  • 特に、ジャッジのテストケースには大きい入力が含まれているので、TLEにならないように注意してください。

入力例1

5
1 4 4 2 3

出力例1

4 2

入力の配列に含まれる各値の出現回数は以下のようになっています。

  • 1 の出現回数は 1 回
  • 2 の出現回数は 1 回
  • 3 の出現回数は 1 回
  • 4 の出現回数は 2 回

出現回数 2 回が最大でその値は 4 なので、4 2 と出力します。

入力例2

6
3 2 3 1 3 2

出力例2

3 3

入力例3

1
1000000000

出力例3

1000000000 1

ヒント

クリックでヒントを開く
  • 「値→出現回数」の関係を dict で管理しましょう。
  • dict への追加・アクセスの計算量は O(1) です。
  • N² は 10¹⁰ なので、O(N²) では TLE になります。
  • N log N ≈ 1.6×10⁶ なので、O(N log N) なら十分間に合います。

テスト入出力

クリックでテスト入出力を見る

テスト入力1

データが大きすぎるため省略

テスト入力2

データが大きすぎるため省略

解答例（Python）

クリックで解答例を見る 
N = int(input())
A = list(map(int, input().split()))

cnt = {}
for x in A:
    if x in cnt:
        # 既に含まれているなら +1
        cnt[x] += 1
    else:
        # 含まれていないなら、1を追加
        cnt[x] = 1

max_cnt = 0    # 出現回数の最大値を保持
ans = -1    # 出現回数が最大になる値を保持
for x in A:
    # 今見ているxの出現回数が、その時点の最大よりも大きければ更新
    if max_cnt < cnt[x]:
        max_cnt = cnt[x]
        ans = x

print(ans, max_cnt)