2 solutions

  • 0
    @ 8 months ago
    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)
    
    
    • 0
      @ 8 months ago

      题面描述:

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

      2024.01.31-秋招-第一题-找出最可疑的嫌疑人

      Information

      ID
      77
      Time
      1000ms
      Memory
      256MiB
      Difficulty
      3
      Tags
      # Submissions
      503
      Accepted
      181
      Uploaded By