题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| import Foundation
class For29Solution {
func moreThanHalfNum(_ n: [Int]) -> Int {
guard n.count > 0 else {
print("n为无效数组")
return -999
}
var hashMap = [Int : Int]()
for r in n {
if hashMap.keys.contains(r) {
hashMap.updateValue(hashMap[r]!+1, forKey: r)
}else {
hashMap.updateValue(1, forKey: r)
}
}
var key: Int? = nil
for k in hashMap.keys {
if hashMap[k]! > n.count/2 {
key = k
}
}
if key == nil {
print("n为无效数组")
return -999
}
return key!
}
}
|
算法思想：某个数字出现的次数大于数组长度的一半，意思就是它出现的次数比其他所有数字出现的次数和还要多。因此我们可以在遍历数组的时候记录两个值：1. 数组中的数字;2. 次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。最后再判断它是否符合条件。
github地址：https://github.com/cubegao/LeetCode
