出现次数超过一半的数

题目描述

给定 $n$ （ $0 < n \leqslant 1000$ ）个整数 $a_1, \dots, a_n$ （ $-50 < a_i < 50$ ），若存在某个值出现次数严格超过一半则输出这个数，否则输出 no。

第一行 $n$ ，第二行 $n$ 个整数。样例：3 / 1 2 2 → 2。

思路

一遍哈希计数得到每个值的出现次数，取最大值；若 2 * times > n（严格过半）则输出该值，否则 no。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 22:45
# update_at: 2026-10-04 10:18

import sys
from collections import Counter


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 数组大小
    count = Counter(next(data) for _ in range(n))  # 每个值的出现次数
    value, times = max(count.items(), key=lambda kv: kv[1])  # 众数及其次数
    # 超过一半：times / n > 1/2 等价于 2 * times > n，用乘法避免浮点
    print(value if 2 * times > n else "no")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 04:41
 * update_at: 2026-10-05 04:41
 */

#include <iostream>
using namespace std;

typedef long long ll;

const int OFFSET = 50;          // 把 -49..49 平移到 0..98 的桶偏移
const int MAXB = 100;           // 桶数量，覆盖值域 [-49, 49] 共 99 个值

int cnt[MAXB];                  // cnt[i] 表示值 (i - OFFSET) 出现的次数

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

    int n;
    if (!(cin >> n)) return 0;  // 数组大小
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;               // 读入数组元素
        cnt[x + OFFSET]++;      // 桶计数
    }

    // 找出现次数最多的值
    int best_id = 0;            // 众数对应的桶下标
    for (int i = 0; i < MAXB; ++i) {
        if (cnt[i] > cnt[best_id]) best_id = i;
    }
    int times = cnt[best_id];   // 众数出现次数
    int value = best_id - OFFSET; // 还原为真实数值

    // 严格过半：times / n > 1/2 等价于 2 * times > n，整数比较避免浮点
    if (2 * times > n) cout << value << "\n";
    else cout << "no\n";

    return 0;
}

出现次数超过一半的数

目录

题目描述

思路

参考代码