題目：數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半掰读，請找出這個數(shù)字猪狈。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,5,4,2}谅年。由于數(shù)字2在數(shù)組中出現(xiàn)了5詞纽甘，超過數(shù)組長度的一半，因此輸出2.
有兩種實(shí)現(xiàn)方式:
1.對數(shù)組排序掖鱼，那么n/2對應(yīng)的數(shù)一定是超過一半的數(shù)字（前提是存在這個數(shù)字）然走，即長度為n的數(shù)組中第n/2大的數(shù)字，O(n).
2.根據(jù)數(shù)組特點(diǎn)戏挡，數(shù)組中一個數(shù)組出現(xiàn)的次數(shù)超過數(shù)組長度的一半芍瑞，即它出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)次數(shù)的和還要多.遍歷數(shù)組時，保留兩個值褐墅，一個是數(shù)組中的一個數(shù)字拆檬，一個是次數(shù).
核心代碼:
<pre><code>`
func moreThanHalfNumber(arr:[Int]) -> Int? {
if arr.count == 0 {
return nil
}
var target:Int = arr[0]
var count:Int = 1
for i in 1..<arr.count {
if count == 0 {
target = arr[i]
count = 1
} else if target == arr[i] {
count += 1
} else {
count -= 1
}
}
return target
}`</code></pre>
測試:
<pre><code>var searchArr:[Int] = [1,2,3,2,2,2,5,4,2] var search:SearchArray = SearchArray() var halfNum:Int? = search.moreThanHalfNum(arr: searchArr) if halfNum != nil { print("FlyElephant--超過一半的數(shù)字---\(halfNum!)") }</code></pre>
