JZ28 陣列中出現次數超過一半的數位

題目描述

陣列中有一個數位出現的次數超過陣列長度的一半，請找出這個數位。例如輸入一個長度為9的陣列{1,2,3,2,2,2,5,4,2}。由於數位2在陣列中出現了5次，超過陣列長度的一半，因此輸出2。如果不存在則輸出0。

思路

思路就是摩爾投票法，原理非常簡單。
這裡推薦一個幫助大家理解的例子。
核心就是對拼消耗。玩一個諸侯爭霸的遊戲，假設你方人口超過總人口一半以上，並且能保證每個人口出去幹仗都能一對一同歸於盡。最後還有人活下來的國家就是勝利。那就大混戰唄，最差所有人都聯合起來對付你（對應你每次選擇作為計數器的數都是眾數），或者其他國家也會相互攻擊（會選擇其他數作為計數器的數），但是隻要你們不要內鬥，最後肯定你贏。最後能剩下的必定是自己人。

連結：https://www.zhihu.com/question/49973163/answer/617122734
來源：知乎

最優解

• 時間O(n)空間O(1)

import java.util.Arrays;
public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
        int value = 0;
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (count == 0) {
                value = array[i];
                count++;
            }else {
                if (value == array[i]) {
                    count++;
                }else {
                    count--;
                }
            }
        }
        if (count == 0) {
            return 0;
        }
        count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == value) {
                count++;
            }
        }
        return count > array.length/2 ? value : 0;
    }
}

發現foreach比用fori多兩毫秒，後來查資料瞭解了一下