数组中出现次数超过一半的数字

一、需求

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字；假设数组是非空的，并且给定的数组总是存在多数元素； 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2

二、暴力法

2.1  思路分析

定义HashMap型变量hm，数组元素为键，对应的元素个数为值；特殊情况：当数组只有一个元素时，直接返回nums[0]；遍历数组，若hm键中已包含数组值，那就将其对应的值加一，然后取出该值，判断是否满足需求，若hm键中不包含数组值，则直接加入，且对应的值为一；

2.2  代码实现

class Solution { public int majorityElement(int[] nums) { HashMap<Integer,Integer> hm = new HashMap<>(); int len = nums.length; for(int i = 0; i < len; i++) { if(hm.containsKey(nums[i])) { hm.put(nums[i],hm.get(nums[i])+1); int count = hm.get(nums[i]); if(count > len/2) return nums[i]; } else { hm.put(nums[i],1); } } return nums[0];//数组只有一个元素的情况 } }

2.3  复杂度分析

时间复杂度为O(N)，其中N为数组中的元素个数；空间复杂度为O(N)，最坏情况下，需要存储N个元素；

三、排序法

3.1  思路分析

对数组进行排序，取中间的元素即为超过一半的数字；

3.2  代码实现

class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } }

3.3  复杂度分析

时间复杂度为O(nlogn)；空间复杂度为O(n)或者O(1)，分别对应线性空间中拷贝数组排序和就地排序；

四、摩尔投票法

4.1  思路分析

假设众数为+1，非众数为-1，那么数组所有元素相加后的结果一定大于0；遍历数组，若count=0，则将当前数字设为当前众数，否则，判断当前数字是否等于当前众数，相等则count+1，不相等则count-1；最后返回当前众数即可。

4.2  代码实现

class Solution { public int majorityElement(int[] nums) { int current_mode = 0; int count = 0; //遍历数组 for(int num : nums) { if(count == 0) { current_mode = num; } count += current_mode == num ? 1 : -1; } return current_mode; } }

4.3  复杂度分析

时间复杂度为O(N)，其中N为数组元素的个数；空间复杂度为O(1)，变量只占用常数大小的空间；