前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2021-08-23:超级水王问题。扩展1:摩尔投票。扩展2:给定一个正数K,返回所有出现次数>N/K的数。

2021-08-23:超级水王问题。扩展1:摩尔投票。扩展2:给定一个正数K,返回所有出现次数>N/K的数。

作者头像
福大大架构师每日一题
发布2021-09-03 15:25:13
4530
发布2021-09-03 15:25:13
举报

2021-08-23:超级水王问题。扩展1:摩尔投票。扩展2:给定一个正数K,返回所有出现次数>N/K的数。

福大大 答案2021-08-23:

扩展1:

1.如果无候选,当前数就是候选,血为1。

2.如果有候选。

2.1.当前数==候选数,血++。

2.2.当前数!=候选数,血--。

最后遍历验证。

时间复杂度:O(N)。

空间复杂度:O(1)。

扩展2:k-1个候选。

最后遍历验证。

代码用golang编写。代码如下:

代码语言:javascript
复制
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
}

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class23/Code04_FindKMajority.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-08-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档