169. 多数元素

题意：

解题思路：

思路：(投票算法) O(n)
1. 定义cnt记录次数，初始化0，num记录答案；
2. 从头开始遍历，如果cnt == 0，则num = v，如果num == v，则增加cnt++[出现次数]，否则cnt--；
3. 遍历结束，剩下的元素则为要找的元素；

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function majorityElement($nums) {
        return $this->majorityElementStack($nums);
        $ret = $nums[0];
        $midV = (int)count($nums) / 2;
        $temp = [];
        foreach ($nums as $item) {
            if (isset($temp[$item])) {
                $temp[$item]++;
                if ($temp[$item] > $midV) $ret = $item;
            } else $temp[$item] = 1;
        }
        return $ret;
    }
    function majorityElement1($nums) {
        $num = $nums[0];
        $cnt = 1;
        for ($i = 1; $i < count($nums); $i++) {
            if ($cnt == 0) {
                $num = $nums[$i];
                $cnt = 1;
            } else if ($nums[$i] == $num) {
                ++$cnt;
            } else --$cnt;
        }
        return $num;
    }
    function majorityElementStack($nums) {
        $stack = [];
        foreach ($nums as $num) {
            if (empty($stack) || end($stack) == $num) {
                $stack[] = $num;
            } else {
                array_pop($stack);
            }
        }
        return end($stack);
    }
}

go代码实现：

func majorityElement(nums []int) int {
    num, cnt := 0, 0
    for _, v := range nums {
        if cnt == 0 {
            num = v
        }
        if num == v {
            cnt++
        } else {
            cnt--
        }
    }
    return num
}