数组中出现次数超过一半的数字——JZ28

https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tags=&title=&difficulty=0&judgeStatus=0&rp=1

 

描述

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。你可以假设数组是非空的,并且给定的数组总是存在多数元素。1<=数组长度<=50000

示例1

输入:

[1,2,3,2,2,2,5,4,2]

复制返回值:

2

复制

示例2

输入:

[3,3,3,3,2,2,2]

复制返回值:

3

复制

示例3

输入:

[1]

复制返回值:

1

 

public class Jz28_MoreThanHalfNum_Solution {


    public int MoreThanHalfNum_Solution(int[] array) {
        HashMap<Integer, Integer> records = new HashMap<>();
        for (int a : array) {
            if (records.containsKey(a)) {
                records.put(a, records.get(a) + 1);
            } else {
                records.put(a, 1);
            }
        }
        int midCount = array.length / 2;
        Iterator<Map.Entry<Integer, Integer>> iterator = records.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, Integer> next = iterator.next();
            if (next.getValue() > midCount) {
                return next.getKey();
            }
        }
        return 0;
    }
}

 

上一篇:Azure 解决方案:如何Add domain的相关建议


下一篇:翻译:《实用的Python编程》03_06_Design_discussion