题面描述:

在某商场的监控记录中，民警正在调查一起盗窃案件，记录下了嫌疑人的出现次数。给定一个嫌疑人编号数组 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);
    }
}

民警侦办某商场店面盗窃率时，通过人脸识别针对嫌局人讲行编号1-100000。现在民警在监控记录中发现有个嫌疑人在被动店面出现的次数超过了所有嫌疑人总出现次数的一半，请帮助民警尽可能高效的找到该嫌疑人的编号。

解答要求

时间限制:C/C++ 1500ms,其他语言:3000ms

内存限制:C/C++ 32MB, 其他语言:64MB

输入

给定一个嫌疑人的标号数组men，其中1<length(men)<1000，嫌人编号满足1<=men[i]<=100000

输出

返回出现次数超过一半的嫌疑人的编号。如果总次数是偶数，例如4，则需要超过2次即最少3次，如果总次数是奇数，例如5，则需要超过2.5，满足条件最少是3次。若没有嫌疑人满足该条件，返回0

样例1

输入

1,2,3,2,2

输出

2

解释

第一行是嫌疑人出现记录，代表1号和3号嫌疑人出现一次，2号嫌疑人出现3次

因为2号嫌疑人出现3次，超过5次的一半，因此2号嫌疑人即为需要寻找的编号，输出2

样例2

输入

1,1,2,2,3,3

输出

0

解释

第一行是嫌疑人出现记录，代表1号、2号和3号嫌疑人各出现2次因为各个嫌疑人均只出现2次，未超过6次的一半，因此没有嫌疑人满足要求，输出0