超级水王问题。扩展1：摩尔投票。扩展2：给定一个正数K，返回所有出现次数>N/K的数。
扩展1：
1.如果无候选，当前数就是候选，血为1。
2.如果有候选。
2.1.当前数==候选数，血++。
2.2.当前数!=候选数，血–。
最后遍历验证。
时间复杂度：O(N)。
空间复杂度：O(1)。
扩展2：k-1个候选。
最后遍历验证。
代码用golang编写。代码如下：
package main
import (
"fmt"
)
func main() {
arr := []int{1, 2, 1, 5, 1, 1, 2}
printHalfMajor(arr)
fmt.Println("--------")
printKMajor(arr, 7)
}
func printHalfMajor(arr []int) {
cand := 0
HP := 0
for i := 0; i < len(arr); i++ {
if HP == 0 {
cand = arr[i]
HP = 1
} else if arr[i] == cand {
HP++
} else {
HP--
}
}
if HP == 0 {
fmt.Println("no such number.")
return
}
HP = 0
for i := 0; i < len(arr); i++ {
if arr[i] == cand {
HP++
}
}
if HP > len(arr)/2 {
fmt.Println(cand)
} else {
fmt.Println("no such number.")
}
}
func printKMajor(arr []int, K int) {
if K < 2 {
fmt.Println("the value of K is invalid.")
return
}
// 攒候选，cands，候选表，最多K-1条记录！ > N / K次的数字，最多有K-1个
cands := make(map[int]int)
for i := 0; i != len(arr); i++ {
if _, ok := cands[arr[i]]; ok {
cands[arr[i]] = cands[arr[i]] + 1
} else { // arr[i] 不是候选
if len(cands) == K-1 { // 当前数肯定不要！，每一个候选付出1点血量，血量变成0的候选，要删掉！
allCandsMinusOne(cands)
} else {
cands[arr[i]] = 1
}
}
}
// 所有可能的候选，都在cands表中！遍历一遍arr，每个候选收集真实次数
reals := getReals(arr, cands)
hasPrint := false
for key, _ := range cands {
if reals[key] > len(arr)/K {
hasPrint = true
fmt.Println(fmt.Sprintf("%d", key) + " ")
}
}
if hasPrint {
fmt.Println("")
} else {
fmt.Println("no such number.")
}
}
func allCandsMinusOne(map0 map[int]int) {
removeList := make([]int, 0)
for key, value := range map0 {
if value == 1 {
removeList = append(removeList, key)
}
map0[key] = value - 1
}
for removeKey, _ := range removeList {
delete(map0, removeKey)
}
}
func getReals(arr []int, cands map[int]int) map[int]int {
reals := make(map[int]int)
for i := 0; i != len(arr); i++ {
curNum := arr[i]
if _, ok := cands[curNum]; ok {
if _, ok2 := reals[curNum]; ok2 {
reals[curNum] = reals[curNum] + 1
} else {
reals[curNum] = 1
}
}
}
return reals
}执行结果如下：
