题解 | #数组中出现次数超过一半的数字#

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

http://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163

  • 第一种方法,数组排序+各元素计数
  • 第二种方法:HashMap统计次数
import java.util.*;
public class Solution {
    // 1.第一种方法,数组排序+各元素计数
    public int MoreThanHalfNum_Solution(int [] array) {
        if (array.length <= 1) {
            return array[array.length - 1];
        }
        // 先进行排序
        Arrays.sort(array);
        int count = 0;
        int half = array.length / 2;
        // 遍历这个有序数组
        for (int i = 0; i < array.length; i++) {
            if (i == 0) { // 第一个元素count置为1
                count++;
            } else {
                // 当前元素与前一个元素相同,则count++
                if (array[i] == array[i - 1]) {
                    count++;
                    // 当前这个元素个数超过了半数,则return这个元素
                    if (count > half) {
                        return array[i];
                    }
                } else {
                    // 如果当前元素与前一个元素不同,则count置为1重新来计数
                    count = 1;
                }
            }

        }
        return -1;
    }

    /*
    // 2.第二种方法:HashMap统计次数
    public int MoreThanHalfNum_Solution(int [] array) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < array.length; i++) {
            map.put(array[i], map.getOrDefault(array[i], 0) + 1);
        }
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue() > (array.length / 2)) {
                return entry.getKey();
            }
        }
        return -1;
    }
    */
}
全部评论

相关推荐

只有一个苍穹外卖外加正在看黑马点评,可以找小厂实习吗,还有我的简历有什么大问题吗
Java抽象小篮子:感觉有点熟悉,问题1是学历,2是没实习经历,3是专业技能写得太少太少了(怎么写可以看我置顶帖),4是仅这一个项目找实习不够看。拷打完毕,简历怎么写可以看我置顶帖子
点赞 评论 收藏
分享
见见123:简历没有啥问题,是这个社会有问题。因为你刚毕业,没有工作经历,现在企业都不要没有工作经历的。社会病了。
点赞 评论 收藏
分享
06-04 18:37
门头沟学院 Java
勇敢的ssr求对象:前面看的有点奔溃,看到只有你是真玩啊,忍不住笑出了声😂
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务