men = list(map(int, input().split(",")))
threshold = len(men) // 2 
h = dict()
flag = True
for man in men:
    h[man] = h.get(man, 0) + 1
    if h[man] > threshold:
        flag = False
        print(man)
        break
if flag:
    print(0)

题面描述:

在某商场的监控记录中，民警正在调查一起盗窃案件，记录下了嫌疑人的出现次数。给定一个嫌疑人编号数组 men，其长度在2到999之间，每个编号在1到100000之间。民警需要确定是否存在某个嫌疑人，其出现次数超过所有嫌疑人总出现次数的一半，并输出该嫌疑人的编号。如果没有任何嫌疑人满足该条件，则返回0。例如，输入 1,2,3,2,2 时，输出为2；而输入 1,1,2,2,3,3 时，输出为0。

思路：模拟

使用哈希表统计每个元素出现的次数

代码说明

1. 输入处理：使用 getline 从标准输入读取一整行字符串，并使用 stringstream 按照逗号分隔这些字符串，将其转换为整数并存储到 nums 向量中。
2. 出现次数统计：利用 map 统计每个编号出现的次数，键为编号，值为出现次数。
3. 条件判断：遍历 map，检查是否有任何编号的出现次数超过 nums 长度的一半。如果找到了符合条件的编号，则输出该编号并结束程序。
4. 结果输出：如果没有找到符合条件的编号，则输出0。

时间复杂度

$O(n)$

代码

C++

#include <iostream>
#include <sstream>
#include <vector>
#include <map>

using namespace std;

int main() {
    // 读取输入的一整行
    string line;
    getline(cin, line);
    stringstream ss(line); // 使用stringstream处理输入
    string item;
    vector<int> nums;

    // 按照逗号分隔输入，将每个数字转换为整数并存储到 nums 向量中
    while (getline(ss, item, ',')) {
        nums.push_back(stoi(item));
    }

    // 使用map统计每个数字的出现次数
    map<int, int> count;
    for (int num : nums) {
        count[num]++;
    }

    // 检查是否有任何数字出现次数超过 nums 长度的一半
    for (auto& kv : count) {
        if (kv.second > nums.size() / 2) {
            cout << kv.first << "\n"; // 输出出现次数最多的数字
            return 0;
        }
    }

    // 如果没有出现次数大于一半的数字，输出0
    cout << 0 << "\n";
    return 0;
}

python代码

from collections import Counter

nums = list(map(int, input().split(','))) # 读入一行数字，以逗号分隔
cnt = Counter(nums) # 用Counter统计每个数字出现的次数

for k in cnt: # 遍历每个数字
    if cnt[k] > len(nums) // 2: # 如果出现次数大于一半
        print(k) # 输出该数字
        break
else:# 如果没有出现次数大于一半的数字
    print(0) 

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 创建 Scanner 对象用于读取输入
        Scanner scanner = new Scanner(System.in);
        
        // 按照逗号分隔输入，存储为字符串数组
        String[] input = scanner.nextLine().split(",");
        
        // 创建一个 HashMap 记录每个数字的出现次数
        Map<Integer, Integer> count = new HashMap<>();
        
        // 遍历输入数组，将字符串转换为整数并计数
        for (String num : input) {
            int n = Integer.parseInt(num);
            count.put(n, count.getOrDefault(n, 0) + 1);
        }
        
        // 遍历 HashMap 检查是否有任何数字出现次数超过数组长度的一半
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            if (entry.getValue() > input.length / 2) {
                System.out.println(entry.getKey()); // 输出出现次数大于一半的数字
                return;
            }
        }
        
        // 如果没有出现次数大于一半的数字，输出0
        System.out.println(0);
    }
}