原题出处：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xwnvrj/

解法一（python）

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        condidate = None
        for num in nums:
            if count == 0:
                condidate = num
            count += 1 if num == condidate else -1
        return condidate

解法二（Rust）

impl Solution {
    pub fn majority_element(nums: Vec<i32>) -> i32 {
        let mut count = 0;
        let mut candidate = None;

        for num in nums {
            if count == 0 {
                candidate = Some(num);
            }
            count += if Some(num) == candidate { 1 } else { -1 };
        }

        candidate.unwrap()
    }
}

解法三（Go）

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

思路：

使用 Boyer-Moore 算法，它的时间复杂度为 O(n)，空间复杂度为 O(1)。该算法的基本思想是维护一个候选众数 candidate 和一个计数器 count，遍历数组时，如果当前数与 candidate 相同，则将计数器加 1，否则将计数器减 1，当计数器减到 0 时，将 candidate 更新为当前数，并将计数器设置为 1。由于众数的出现次数大于 ⌊n/2⌋，因此遍历完整个数组后 candidate 中保存的就是众数。

解法四（Go）

import "sort"
func majorityElement(nums []int) int {
    sort.Ints(nums)
    return nums[len(nums)/2]
}

思路：将数组排序，元素数量超过二分之一的元素一定会出现在中间。我们直接获取即可。

解法五（java）

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap();
        int count = nums.length/2;
        for (int i = 0 ; i < nums.length; i++) {
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
            if (map.get(nums[i]) > count) {
                return nums[i];
            }
        }

        return -1;
    }
}

思路：哈希统计法，就是我们将数组元素的每一个值作为一个map的key，value作为元素出现的次数，当map中出现的元素次数超过一半了，我们就直接返回当前元素的值即可。