【数据结构和算法】排序，Map，2种方式解决

1，先排序

先排序，然后在挨着统计每个数字的个数

    public int MoreThanHalfNum_Solution(int[] array) {
        if (array.length == 1)
            return array[0];
        //先排序
        Arrays.sort(array);
        int count = 1;
        int num = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] == num) {//还是原来的数字就加1
                count++;
                if (count > array.length / 2)
                    return array[i];
            } else {//遇到了新的数字，都重新赋值
                count = 1;
                num = array[i];
            }
        }
        return 0;
    }

2，使用Map解决

还可以使用Map来解决，map的key存放的是数组中的元素，value是数组中元素的个数，把数组中元素不断的存放到map中，如果某个元素的个数大于数组长度的一半，直接返回。

    public int MoreThanHalfNum_Solution(int[] array) {
        Map<Integer, Integer> counts = new HashMap<>();
        int length = array.length;
        for (int i = 0; i < length; i++) {
            int count = counts.getOrDefault(array[i], 0) + 1;
            //如果某个数字出现的个数已经超过数组的一半，自己返回
            if (count > length / 2)
                return array[i];
            counts.put(array[i], count);
        }
        return 0;
    }

我把部分算法题整理成了PDF文档，截止目前总共有900多页，大家可以下载阅读
链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666

如果觉得有用就给个赞吧，还可以关注我的《牛客博客》查看更多的详细题解