题解 | #数组中出现次数超过一半的数字#

数组中出现次数超过一半的数字

http://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163

由于有一个数字在数组中出现的次数超过了一半。则我们每次都选出两个不同的数字,将其从数组中去掉,直到数组中只剩下一个数,或多个相同的数,就是要找的众数。
实际操作中,使用一个变量candi保存当前准备比较的数,用一个变量count保存这个准备比较的数还剩多少个才能完全从数组中去掉。每次比较时,若count为0,说明需要选出第一个数,准备与另一个不同的数一同从数组中去掉。当count不为0,若当前数与candi数相等,则count++,说明candi数又重复了一次,需要count++次才能从数组中完全去除。当当前数不等于candi时,count--,表明将该数与一个candi从数组中去除。最终candi保存的数就是需要寻找的众数。

空间复杂度O(1),时间复杂度O(n)。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int candi = 0;
        int count = 0;
        for(int i = 0;i < numbers.size();i++){
            if(count == 0){
                candi = numbers.at(i);
                count++;
            }
            else if(candi == numbers.at(i)){
                count++;
            }
            else{
                count--;
            }
        }
        return candi;
    }
};
全部评论

相关推荐

06-26 15:33
青岛工学院 Java
积极的秋田犬要冲国企:他现在邀请我明天面试
点赞 评论 收藏
分享
06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
评论
4
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务