169.多数元素

题目

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

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

解题思路

方法一：使用HashMap集合，统计每个元素的出现次数，返回出现次数大于数组长度一半的元素。
时间复杂度：O(n)，空间复杂度O(n)
方法二：排序，由于一定存在多数元素，直接返回中间元素就是多数元素。
时间复杂度：O(nlogn)，空间复杂度：O(logn)
方法三：摩尔投票，思想是多数元素与其他元素抵消，候选元素记录当前的多数元素，计数器归0时需要更新候选元素。
时间复杂度：O(n)，空间复杂度O(1)

代码

方法一：HashMap集合

class Solution {public int majorityElement(int[] nums){// 1. 将数组元素及其出现的次数存放在Map集合中Map<Integer,Integer> countMap = new HashMap<>();for(int num : nums){countMap.put(num, countMap.getOrDefault(num, 0) + 1);}// 2. 遍历Map集合，要将Map集合转换为entry对象for(Map.Entry<Integer, Integer> entry : countMap.entrySet()){// 3. 如果对应entry对象的value大于数组长度的一般直接返回对应的keyif(entry.getValue() > nums.length / 2){return entry.getKey();}}return -1;}
}

方法二：排序法

class Solution {public int majorityElement(int[] nums) {// 1. 对数组进行排序Arrays.sort(nums);// 2. 返回中间的元素return nums[nums.length/2];}
}

方法三：摩尔法

class Solution {public int majorityElement(int[] nums) {int count = 0;int condidate = 0;for (int num : nums) {// 1. 如果计数器为0，候选元素为当前元素if (count == 0) {condidate = num;}// 2. 遍历时更新count的值count += (condidate == num ? 1 : -1);}return condidate;}
}