73.数组中出现次数超过一半的数字
知识点：数组；哈希；占领地思想；
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解法一：
最容易想到的，直接遍历数组，对于每一个元素，将其他的遍历一遍，看有没有和它一样的，相当于遍历两次数组，大于一半直接返回；
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
for(int i = 0; i < array.length; i++){
int count = 0;
for(int j = 0; j < array.length; j++){
if(array[j] == array[i]){
count++;
}
}
if(count > array.length / 2){
return array[i];
}
}
return 0;
}
}
时间复杂度O(n^2);
解法二：
这种找重复数字的，其实往往都会用到Hash的知识，由于我们又得需要一个值去对应存每个值有几个，所以采用map的<key,value>这种对应键值来保存；
import java.util.*; //注意要熟悉HashMap的常用方法；
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int k : array){
if(!map.keySet().contains(k)){
map.put(k,1);
}else{
map.put(k,map.get(k)+1);
}
}
for(int k : map.keySet()){
if(map.get(k) > array.length / 2){
return k;
}
}
return 0;
}
}
这样只遍历一遍数组就可以，时间复杂度O(n);
解法三：
抢阵地思想：试想现在我们有一个土坡需要占领，然后有好几个队都要占领这个土坡，而且每一个队能够消灭其他对一个人，也就是极限一换一；如果有一个队有超过总人数一半的人数，那是不是肯定最好他们能占领土坡(即使你们不内讧全部来跟我换我也能赢，就是人多就是玩)，现在我们就可以用这个思想去解，依次往土坡上冲，谁活到最好谁就赢。
注意：有超过一半的一定能留在最后，但是留在最后的不一定超过一半，一个队就1个，你们全都1V1换完了，那最后我上，那就是我了，所以最后还要判断一下；
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int num = array[0]; //先让第一个人冲上去占领土坡；
int count = 1; //记录每次土坡上的人数；
for(int i = 1; i < array.length; i++){
if(count == 0){
num = array[i];
count++;
}else if(array[i] == num){
count++;
}else{
count--;
}
}
if(count > 0){
int times = 0;
for(int i = 0; i < array.length; i++){
if(array[i] == num){
times++;
}
}
if(times > array.length / 2){
return num;
}
return 0;
}
return 0;
}
}
时间复杂度：O(n);