题目
- 给定一个长度为n的数组，找出主要元素，主要元素的定义是在数组中出现的次数超过n/2
- 假设数组非空并且给定的数组中总是存在这样一个数
- 举例，输入[3,2,3]输出3
解题思路1
- 双重循环，内存循环遍历获得外层循环的值nums[i]出现的次数，然后和n/2比较，如果比n/2大就返回这个值，否则一直遍历到结束
- 时间复杂度O(n^2),代码不贴了就是一个双重循环
解题思路2
- 设置一个HashMap，键表示num[i],值表示num[i]出现的次数，然后遍历HashMap找到出现次数最多或者是大于n/2的那个数返回
- 时间复杂度O(n),空间复杂度O(n)
解题思路3
- 先对数组进行排序，根据题目要求，返回的是超过n/2的数据，那么排序后n/2的数据一定是我们要的数字，代码很简单两行实现
- 时间复杂度O(nlogn),空间复杂度O(1)或者O(n)
代码三
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
解题思路4(参考官方思路，没想到的方法)
- 投票算法，根据我们的需求可以选出一个num作为candidate，然后我们开始对数组进行遍历，如果这个数等于candidate那么我们就将票数加1，如果不等于就票数减一，如果票数为0那么我们就设定新的值为candidate,根据要求必然存在大于n/2那么最后票数值肯定大于0
代码实现
class Solution {
public int majorityElement(int[] nums) {
int candidates = nums[0];
int times = 0;
for (int num : nums) {
if (times == 0) candidates = num;
times += (num == candidates) ? 1 : -1;
}
return candidates;
}
}
