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

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

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

第六十九题 408经典数组题
原理要自己理解
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        // 408题
        // 方法一:遍历 存hash,再遍历,返回hash的值大于长度一半的值(空间复杂度超了)
        // 假设第一个就是,从前向后遍历,统计次数,出现不一样的就次数-1,如果说减完小于0了,则替换当前比较值为新的结果
        // 直到遍历结束,结果肯定是count>=0的一个数
        // 原理:
        // 因为要找的是出现次数超过一半的数字,所以说,一个这个数字和其他数字两两删除,剩下的肯定是这个超过一半的数字
        // 所以从前向后遍历,出现超过一般的数字肯定会是留到最后的数字。
        
        int count=0;
        int ans=numbers[0];
        // 向后遍历
        for(int i=0;i<numbers.size();i++)
        {
            // 是预测的就+1
            if(numbers[i]==ans)
                count++;
            else{
                // 不是预测的就-1,如果结果小于0了,则重新预测
                count--;
                if(count<0){
                    ans=numbers[i];
                    count=1;
                }
            }
        }
        return ans;
    }
};
题解 文章被收录于专栏

一遍做剑指offer 一边保存做题步骤 并附带详细注释哦

全部评论

相关推荐

兄弟们,实习都是在接各种api,该怎么包装简历
仁者伍敌:感觉我自己做小项目也是各种api啊,我要怎么包装简历
点赞 评论 收藏
分享
牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
06-23 11:43
门头沟学院 Java
allin校招的烤冷...:我靠,今天中午我也是这个hr隔一个星期发消息给我。问的问题还是一模一样的😅
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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