題目：數(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。
初步思路：將數(shù)組中的元素進行排序拄养，統(tǒng)計每個數(shù)字出現(xiàn)的次數(shù)离斩，然后找出出現(xiàn)次數(shù)超過一半的那個數(shù)字。這樣的話排序的時間復雜度將是O(nlogn)瘪匿。
在面試中跛梗，這樣的時間復雜度可能不會令面試官滿意，是否存在速度更快的算法呢柿顶？
解法：數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組的一半等價于它出現(xiàn)的次數(shù)要比其他所有的數(shù)字出現(xiàn)的次數(shù)之和都要大茄袖。我們在遍歷數(shù)組的時候保存兩個值：一個是數(shù)組中的一個數(shù)字；另一個是次數(shù)嘁锯。如果我們遍歷的下一個數(shù)字和我們之前的數(shù)字一樣，則次數(shù)+1聂薪；如果不一樣家乘，則次數(shù)-1。這樣的話藏澳，我們的算法的時間效率則是O(n)仁锯。
基本實現(xiàn)
但是，我們還要考慮到一些無效的輸入翔悠。數(shù)組是否有效业崖？數(shù)組中是否存在出現(xiàn)次數(shù)超過數(shù)組長度一半的數(shù)字？這些都要考慮到蓄愁。
有效性判斷方法
這樣才算一個完整的實現(xiàn)双炕。
完整代碼
具體請參考《劍指Offer》。
