169. Majority Element

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    var m=[];
    for(var i=0;i<nums.length;i++)
    {
        if(m[nums[i]])
        m[nums[i]]++;
        else 
        m[nums[i]]=1;
        if(m[nums[i]]>nums.length/2)
        {
        return nums[i];
        }
    }
};

看到两个比较好的想法

Java，比较简洁，排序后的中间的数必定是答案

public class Solution {
    public int majorityElement(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
    }
}

Java，时间复杂度O（n），空间复杂度O（1）,

public class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count++;
            } else if (candidate == num) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
}