【剑指offer】-28-数组中出现次数超过一半的数字

方法一：Map法。时间复杂度：O（n），空间复杂度：O（n）。

import java.util.*;
public class Solution{
    public int MoreThanHalfNum_Solution(int[] array) {
        if (array.length == 0 || array == null) return 0;
        Map<Integer, Integer> map = new HashMap<>();
        int maxCount = 0;
        int val = 0;
        for (int i = 0; i < array.length; i++) {
            int currentKey = array[i];
            Integer value = map.get(currentKey);
            if (value != null) {
                map.put(currentKey, value + 1);
                if (value + 1 > maxCount) {
                    maxCount = value + 1;
                    val = currentKey;
                }
            } else {
                map.put(currentKey, 1);
                if (maxCount < 1) {
                    maxCount = 1;
                    val = currentKey;
                }
            }
        }
        return (maxCount > array.length / 2) ? val : 0;
    }
}

方法二：同归于尽，相互抵消法。时间复杂度：O（n），空间复杂度：1。

• 阵地攻守的思路：第一个数字作为士兵，count=1，遇到一个相等的数字即友军则count++，遇到不同的数字即敌军则count--，此时当count==0的时候，选用下一个数字作为友军且count=1。直到最后若count >1，那么只有这个数字才有可能是超过一半的数字，因为若一个数字他超过数组一半，那么它必定能活到最后。
• 上一步是找出出现最多的数字，再遍历数组判断这个数字出现的次数是否大于一半。

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0)return 0;
        int preValue = array[0];//用来记录上一次的记录
        int count = 1;//preValue出现的次数（相减之后）
        for(int i = 1; i < array.length; i++){
            if(array[i] == preValue)
                count++;
            else{
                count--;
                if(count == 0){
                    preValue = array[i];
                    count = 1;
                }
            }
        }
        int num = 0;//需要判断是否真的是大于1半数，这一步骤是非常有必要的，因为我们的上一次遍历只是保证如果存在超过一半的数就是preValue，但不代表preValue一定会超过一半
        for(int i=0; i < array.length; i++)
            if(array[i] == preValue)
                num++;
        return (num > array.length/2)?preValue:0;

    }
}