LeetCode 169. 多数元素

题目简述：找到一个数组中的“多数元素”，即在数组中出现次数大于数组长度一半的元素。假设数组总是非空的，并且给定的数组总是存在多数元素。

1. 哈希法

1.1原理

利用哈希表来记录每个元素出现的次数。

1. 遍历整个数组，对每个元素进行计数，使用哈希表记录每个元素出现的次数。
2. 接着遍历哈希表中的每个元素，寻找出现次数大于数组长度一半的元素。

1.2 代码

public int majorityElement(int[] nums) {
    Map<Integer,Integer> counts = new HashMap<>();
    int maxNum = 0;
    int maxCount = 0;
    for (int i:nums){
        int count = counts.getOrDefault(i,0) + 1;
        counts.put(i,count);

        if (count>maxCount){
            maxNum = i;
            maxCount = count;
        }
    }
    return maxNum;
}

2. 摩尔投票法

2.1 原理

摩尔投票法是一种巧妙的解决方法，其核心思想是利用元素的抵消。

1. 将数组的第一个元素作为候选人，初始票数为1。
2. 遍历数组，对于遇到的每个元素：
   • 如果当前元素与候选人相同，则票数加1；
   • 如果当前元素与候选人不同，则票数减1。
3. 当票数减至0时，更换候选人为当前元素，并将票数重置为1。
4. 遍历完数组后，最终的候选人即为多数元素。

2.2 为何摩尔投票法可行

摩尔投票法之所以可行，是因为多数元素的个数大于数组长度的一半。在遍历数组时，每次遇到不同的元素时，它们两两相互抵消，而多数元素仍然会保留在最终的候选人中。

2.3 代码

public int majorityElement(int[] nums) {
    int candidate = nums[0];
    int count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == candidate) {
            count++;
        } else {
            count--;
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            }
        }
    }
    return candidate;
}

简化写法

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