LeetCode-算法-多数元素

力扣题目地址：https://leetcode-cn.com/problems/majority-element/

首先看题目：
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

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

示例：

示例 1:
输入: [3,2,3]
输出: 3

示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2

解决思路：
第一种解法：暴力**法
我的想法是首先将数组里面的元素都放入一个数据结构中，遇到重复的值就加一；思来想去感觉 Map 比较适合我的需求。将元素值作为key；循环遍历数组，如果map中没有这个key则将key存入map中，并将value设置为一，；如果存在key，则将value值加一然后存入map。
然后我们循环遍历出map中value值最大的元素，并返回。

第二种解法：数学方法
首先，我们得到的是一个无序数组，如果我们能够得到一个有序的数组，那么多数元素一定在该数组的 n/2 处有一个；假设考虑两种极限情况，首先明白初始条件多数元素大于 n/2 个，所以有序数组无论从数组中最大的还是最小的，他一定包含 n/2 这个位置。所以我们直接返回有序数组中的第 n/2 个元素即可。

代码实现：

	/**
     * 第一种：暴力**法   查找多数元素
     * https://leetcode-cn.com/problems/majority-element/
     * @param nums
     * @author Geyuxuan 2020-03-13 17:50:09
     * @return int
     */
    public int majorityElement(int[] nums) {
        //将元素放入map中
        Map<Integer,Integer> numsMap = new HashMap<>(nums.length);
        for (Integer item : nums){
            if(numsMap.containsKey(item)){
                int times = numsMap.get(item);
                numsMap.put(item,++times);
            }else{
                numsMap.put(item,1);
            }
        }
        //获取最大次数的元素
        int maxKey = -1;
        //获取最大元素的最大次数
        int maxValue = 0;
        for (Map.Entry<Integer,Integer> entry : numsMap.entrySet()){
            //获取最大值
            if(entry.getValue() > maxValue){
                maxValue = entry.getValue();
                maxKey = entry.getKey();
            }
        }
        //如果数组元素最大重复数小于 多数规则，返回失败
        if(maxValue <= nums.length/2){
            return -1;
        }
        return maxKey;
    }

    /**
     * 第二种：数学方法，如果存在多数，那么排序后，他一定在 n/2 上
     * 查找多数元素  
     * https://leetcode-cn.com/problems/majority-element/
     * @param nums
     * @author Geyuxuan 2020-03-13 17:50:09
     * @return int
     */
    public int majorityElement1(int[] nums) {
    	//数组排序
        Arrays.sort(nums);
        //取 n/2 位置的值
        return nums[nums.length/2];
    }

不忘初心，砥砺前行。