题目
解析
一道求众数的题目，原先的想法很简单，求出每一个数字出现的次数并放入一个数组中，最后再遍历该数组找到最大的即可，（所以就出现了定义一个类，包含val和count两个属性，然后再创建对象放入集合中一一比较这种非常非常慢的算法，虽然可以实现结果，但是却耗费了很多时间），后来我利用了hashmap，大致思路和刚才说的一样，算法如下：（当然也超时了）
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int count = 0;
for (int j = i; j < nums.length; j++) {
if (nums[i] == nums[j]) {
count++;
}
}
map.put(nums[i], count);
}
Iterator iter = map.entrySet().iterator();
int max = 0;
int maxNum = nums[0];
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
if ((int) val > max) {
max = (int) val;
maxNum = (int) key;
}
}
return maxNum;
}
最后我在查资料的时候发现了一种新的算法——“摩尔投票法”
程序开始之前，元素c为空，f(c)=0。遍历数组A:
- 如果f(c)为0，表示截至到当前子数组，并没有候选元素。也就是说之前的遍历过程中并没有找到超过半数的元素。那么，如果超过半数的元素c存在，那么c在剩下的子数组中，出现次数也一定超过半数。因此我们可以将原始问题转化为它的子问题。此时c赋值为当前元素, 同时f(c)=1。
- 如果当前元素A[i] == c, 那么f(c) += 1。(没有找到不同元素，只需要把相同元素累计起来)
- 如果当前元素A[i] != c，那么f(c) -= 1 (相当于删除1个c)，不对A[i]做任何处理(相当于删除A[i])
- 如果遍历结束之后，f(c)不为0，则找到可能元素。
- 再次遍历一遍数组，记录c真正出现的次数，从而验证c是否真的出现了超过半数。上述算法的时间复杂度为O(n)，而由于并不需要真的删除数组元素，我们也并不需要额外的空间来保存原始数组，空间复杂度为O(1)。
代码如下：
/**
* 算法基础：摩尔投票法
*
* @param nums
* @return
*/
public int majorityElement(int[] nums) {
int majority = -1;
int count = 0;
for (int num : nums) {
if (count == 0) {
majority = num;
count++;
} else {
if (majority == num) {
count++;
} else {
count--;
}
}
}
int counter = 0;
if (count <= 0) {
return -1;
} else {
for (int num : nums) {
if (num == majority) counter++;
}
}
if (counter > nums.length / 2) {
return majority;
}
return -1;
}
