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.

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    var num = nums.length;
    var count = 0;
    var item;
    for (var i = 0; i<num; i++) {
        if (count === 0) {
            item = nums[i];
        }
        if (nums[i]===item) 
            count++;
        else
            count--;
    }
    return item;
};

我們從數(shù)組第一個(gè)開(kāi)始找起
如果當(dāng)前候選人的計(jì)數(shù)是0，就把當(dāng)前這個(gè)元素當(dāng)成候選人
如果當(dāng)前這個(gè)元素和候選人相同，候選人計(jì)數(shù)就加1，不同就減一，如果減至0，就意味著當(dāng)前候選人在之前的元素中被抵消完了，在已經(jīng)檢查過(guò)的元素中，該候選人不滿足大于n/2的條件。

Majority Element II

Given an integer array of size n, find all elements that appear more than ? n/3 ?
times. The algorithm should run in linear time and in O(1) space.
現(xiàn)在要求找到個(gè)數(shù)大于n/3的，這樣的數(shù)應(yīng)該最多只有兩個(gè)。我們拓展一下剛才的方法，使用兩個(gè)指針

var majorityElement = function(nums) {
    var num = nums.length;
    if (num === 0)
        return [];
    var item1,item2;
    var c1 = 0;
    var c2 = 0;
    for (let i = 0;i < num;i++) {
        //如果C1和C2都是0，優(yōu)先給C1
        if (c1 === 0&&c2 === 0) {
            item1 = nums[i];
            c1++;
        //如果C1不是0，C2是0
        } else if (c1 !== 0&&c2 === 0) {
            //檢查是不是C1該記錄的元素
            //是就分給C1，不是就給C2
            if (item1 === nums[i]) {
                c1++;
            } else {
                item2 = nums[i];
                c2++;
            }
        //同理
        } else if (c1 === 0&&c2 !== 0) {
            if (item2 === nums[i]) {
                c2++;
            } else {
                item1 = nums[i];
                c1++;
            }
        //如果C1，C2此時(shí)都有分配，那檢查當(dāng)前元素屬于誰(shuí)
        } else {
            if (item2 === nums[i]) {
                c2++;
            } else if (item1 === nums[i]) {
                c1++;
            //如果誰(shuí)都不屬于，那就都減
            } else {
                c1--;
                c2--;
            }
        }
        //更簡(jiǎn)單的判斷方法，思想其實(shí)一樣的
        // if (item1 === nums[i]) {
        //     c1++;
        // } else if (item2 === nums[i]) {
        //     c2++;
        // } else if (c1 === 0) {
        //     item1 = nums[i];
        //     c1++;
        // } else if (c2 === 0) {
        //     item2 = nums[i];
        //     c2++;
        // } else {
        //     c1--;
        //     c2--;
        // }
    }
    c1 = 0;
    c2 = 0;
    //現(xiàn)在只能說(shuō)item1和2是出現(xiàn)次數(shù)最多的
    //找到當(dāng)前item1和item2出現(xiàn)的總次數(shù)，看看是不是符合題目的要求
    for (let i = 0; i < num; i++) {
        if (nums[i] == item1)
            c1++;
        else if (nums[i] == item2)
            c2++;
    }
    var res = [];
    if (c1 > num / 3)
        res.push(item1);
    if (c2 > num / 3)
        res.push(item2);
    return res;
};