Majority Element

思路一: map

public int majorityElement(int[] nums) {
    if (nums.length == 1) return nums[0];

    Map<Integer, Integer> map = new HashMap<>();
    int N = nums.length / 2;
    for (int num : nums) {
        if (map.containsKey(num)) {
            Integer n = map.get(num);
            if (n + 1 > N) {
                return num;
            }
            map.put(num, n + 1);
        } else {
            map.put(num, 1);
        }
    }

    throw new RuntimeException("error");
}

思路二: 排序,中间的数字一定是求解,用反证法可以证明。这个思路一开始没有想到

思路三: 随机取一个数,然后验证。这种思路也很巧妙,但是复杂度不好控制,运气不好可能要跑很长时间

思路四: 分治法,把数组分为两半,其中一边的值必然有 Majority Element,用反证法可以证明。这样复杂问题就可以越分越小,分治法的思想很巧妙

思路五: Boyer-Moore 投票算法

public int majorityElement(int[] nums) {
    int count = 0;
    Integer candidate = null;
    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }
    return candidate;
}

原文地址:http://www.cnblogs.com/iyiluo/p/16817480.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性