題目描述

數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半，因此輸出2。如果不存在則輸出0。

笨豬直腦筋，讀題覺得本身也只需要遍歷一遍列表（不算sort）嘛，所以就很直腦筋的寫出了答案，但是看了一下答案覺得思路太巧妙了記錄一下：

兩種思路。第一種思路，出現(xiàn)次數(shù)超過一半的數(shù)字，不管如何，必然這個數(shù)字位于數(shù)組中間的位置，因此可以采用類似于快排的劃分的方法，找到位于數(shù)組中間的位置的數(shù)字，然后在順序檢索是否這個數(shù)字出現(xiàn)次數(shù)超過一半。第二種思路根據(jù)數(shù)組的特點，出現(xiàn)次數(shù)超過一半的數(shù)，他出現(xiàn)的次數(shù)比其他數(shù)字出現(xiàn)的總和還要多，因此可以最開始保存兩個數(shù)值：數(shù)組中的一個數(shù)字以及它出現(xiàn)的次數(shù)，然后遍歷，如果下一個數(shù)字等于這個數(shù)字，那么次數(shù)加一，如果不等，次數(shù)減一，當次數(shù)等于0的時候，在下一個數(shù)字的時候重新復制新的數(shù)字以及出現(xiàn)的次數(shù)置為1，直到進行到最后，然后再驗證最后留下的數(shù)字是否出現(xiàn)次數(shù)超過一半，因為可能前面的次數(shù)依次抵消掉，最后一個數(shù)字就直接是保留下來的數(shù)字，但是出現(xiàn)次數(shù)不一定超過一半。

其中第一種思路覺得十分巧妙，第二種思路自己覺得好像沒有必要，但是遍歷次數(shù)確實是最少的。在此主要記錄第一種思路。