数组-14-LeetCode169题-多数元素

LeetCode169题 -> 多数元素

1. 题目描述

• 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。可以假设数组是非空的，并且给定的数组总是存在多数元素。

• 示例

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

2. 解题思路

• 思路1：HashMap法
  • ①利用HashMap来存储数组中每个元素及出现的次数，键表示nums[i]，值表示nums[i]出现的次数；
  • ②遍历数组将数组中的每个元素加入这个HashMap中；
  • ③判断HashMap中大于nums.length/2的值，返回该值对应的键。
• 思路2：摩尔投票法
  • ①初始一个候选众数candidate，和它出现的次数count;
  • ②遍历数组nums，判断每个元素nums[i]之前，如果count是0，就将candidate的值等于nums[i]，然后判断nums[i];
  • ③如果nums[i] == candidate，count加1；否则，count减1；
  • ④nums遍历完后，candidate即为数组的众数。

3. 代码实现

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

public class MajorityElement {
    /**
     * 1.HashMap法
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums){
        Map<Integer,Integer> map = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
            if(map.get(nums[i]) > (n/2)){
                return nums[i];
            }
        }
        return 0;
    }

    /**
     * 2.摩尔投票法
     * @param nums
     * @return
     */
    public static int majorityElement2(int[] nums){
        int candidate = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if(count == 0){
                candidate = nums[i];
            }
            if(nums[i] == candidate){
                count++;
            }else{
                count--;
            }
        }
        return candidate;
    }

    public static void main(String[] args) {
        int[] nums = {2,2,1,1,1,2,2};
        System.out.println(majorityElement2(nums));
    }
}