算法-多数元素（力扣-169）难度：简单

• 题目描述：
• • 示例1：
  • 示例2：
  • 进阶：
  • • 解题思路：

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 数组长度一半 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

输入： nums = [3,2,3]
输出：3

输入： nums = [2,2,1,1,1,2,2]
输出：2

• 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

• 简单粗暴法：

简单粗暴的方法就是遍历数组，统计各个元素出现的次数，找到符合条件的元素

1. 使用Map保存元素出现的次数，如果次数大于数组的一半则返回该元素

package com.javaxiang.leetcode;

import java.util.HashMap;
import java.util.Map;

class Solution169 {
    public int majorityElement(int[] nums) {
        Map map = new HashMap<>();
        for(int num : nums){
            if(!map.containsKey(num)){
                map.put(num,1);
            }else{
                Integer count = map.get(num);
                map.put(num,count+1);
            }
            Integer count = map.get(num);
            if(count > nums.length >> 1) return num;
        }
        return -1;
    }
}

2. 使用Java8中的stream流进行分组统计

package com.javaxiang.leetcode;

import java.util.Arrays;
import java.util.function.Function;
import java.util.stream.Collectors;

class Solution169 {
    public int majorityElement(int[] nums) {
		int[] res = new int[]{-1};
        Arrays.stream(nums)
                .boxed()
                .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
                .forEach((k,v)-> {
                    if (v > nums.length >> 1) res[0] = k;
                });
        return res[0];
	}
}

• 摩尔投票法：
  由于题目总是出现多数元素，则可使用摩尔投票法：

• 假定第一个元素是多数元素（目标元素），初始化计数器为1；
• 遍历数组，遇到和目标元素相同的元素则计数器加一；
• 遇到和目标元素不相同的则计数器减一；
• 如果计数器减到零，则改变目标元素，并且将计数器初始化为1；
• 遍历完数组后，目标元素的值即为多数元素。

package com.javaxiang.leetcode;

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

摩尔投票法仅遍历数组一次，时间复杂度为 O(n)，仅定义了两个局部临时变量，所以空间复杂度为 O(1) 。