2017校招-好未来：n个数里出现次数大于等于n/2的数

发表于 更新于 分类于 阅读次数： Disqus： 本文字数： 0 阅读时长 ≈ 1 分钟

题目描述

输入n个整数，输出出现次数大于等于数组长度一半的数。

输入描述

每个测试输入包含 n个空格分割的n个整数，n不超过100，其中有一个整数出现次数大于等于n/2。

输出描述

输出出现次数大于等于n/2的数。

示例1

输入
3 9 3 2 5 6 7 3 2 3 3 3
输出
3

解题思路

由于这个题目是要求输出出现次数大于等于数组长度一半的数，而不是大于数组长度的数，所以这里是不能用删除法：即每次删除两个不相同数，最后剩下的即是要求的数。不过还是可以用Map的方法来做。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> nums = new ArrayList<>();
        while(sc.hasNext()) {
            nums.add(sc.nextInt());
        }
        Map<Integer, Integer> numTimes = new HashMap<>();
        for (Integer ele : nums) {
            numTimes.put(ele, numTimes.getOrDefault(ele, 0) + 1);
        }
        int max = 0;
        int num = 0;
        for (Integer ele : numTimes.keySet()) {
            if (numTimes.get(ele) > max) {
                max = numTimes.get(ele);
                num = ele;
            }
        }
        System.out.println(num);
    }
}