題目：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字。

例如，輸入一個(gè)長(zhǎng)度為9的數(shù)組{1，2，3，2，2，2，5，4，2}。由于數(shù)字2再數(shù)組中出現(xiàn)了5次，超過數(shù)組長(zhǎng)度的一半，因此輸出2。

初步思路：將數(shù)組中的元素進(jìn)行排序，統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)的次數(shù)，然后找出出現(xiàn)次數(shù)超過一半的那個(gè)數(shù)字。這樣的話排序的時(shí)間復(fù)雜度將是O(nlogn)。

在面試中，這樣的時(shí)間復(fù)雜度可能不會(huì)令面試官滿意，是否存在速度更快的算法呢？

解法：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組的一半等價(jià)于它出現(xiàn)的次數(shù)要比其他所有的數(shù)字出現(xiàn)的次數(shù)之和都要大。我們?cè)诒闅v數(shù)組的時(shí)候保存兩個(gè)值：一個(gè)是數(shù)組中的一個(gè)數(shù)字；另一個(gè)是次數(shù)。如果我們遍歷的下一個(gè)數(shù)字和我們之前的數(shù)字一樣，則次數(shù)+1；如果不一樣，則次數(shù)-1。這樣的話，我們的算法的時(shí)間效率則是O(n)。

基本實(shí)現(xiàn)

但是，我們還要考慮到一些無(wú)效的輸入。數(shù)組是否有效？數(shù)組中是否存在出現(xiàn)次數(shù)超過數(shù)組長(zhǎng)度一半的數(shù)字？這些都要考慮到。

有效性判斷方法

這樣才算一個(gè)完整的實(shí)現(xiàn)。

完整代碼

具體請(qǐng)參考《劍指Offer》。