LeetCode169. Majority Element解答

天气冷了 ，有男朋友的抱男朋友，有女朋友的抱女朋友，而我就比较牛逼了

我不冷

先来看一下题目

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array. 题目大意是:给你一个长度为n的数组，要求你找到它的众数，众数就是在这个数组中出现次数超过n/2次数的元素，你可以假定这个数组是非空的，并且它一定会有一个满足条件的众数。 Credits: Special thanks to @ts for adding this problem and creating all test cases. #解题思路 要找众数，必然需要两个变量，一个用来保存当前候选的数字，另一个用来保存数字出现的频率，我的做法是使用一个哈希表（Hashtable）用来维护所有的数组以及它们分别出现的频率，然后在这个哈希表中寻找出现频率最大的。 代码如下：

import java.util.Hashtable;
class Solution {
    public int majorityElement(int[] nums) {
        Hashtable table=new Hashtable(nums.length/2);
        int curr,currmax=0;
        int currcount=0;
        for(int i=0;i

更好的算法

我及其喜欢这个算法，代码简洁高效，只用了一遍遍历。不过它的核心思想我还没有参透，用这个代码一步步调试过，但是没有时间细细思考为什么这个算法可以得到正确答案，以后有时间了再来挖坟

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int major = 0;
        for(int val : nums){
            if(count == 0){
                major = val;
                count =1;
                continue;
            }
            if(major == val) {
                count++;
            }
            else {
                count--;
            }
        }
        return major;
    }
}