《剑指offer》-数组中出现次数超过一半的数字

简介: /*数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
/*
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
*/

class Solution {
public:
    /*
    最开始的想法:排序后,假如存在元素满足题目条件,那么中间位置的元素就是这样的元素,那么双向增长,判断增长停滞点之间的长度
    缺点是复杂度过高
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        sort(numbers.begin(), numbers.end());
        if(numbers.size()==0){
            return 0;
        }
        if(numbers.size()==1){
            return numbers[0];
        }
        int mid = (numbers.size()-1)/2;
        int low=mid, high=mid+1;
        while(low>=0 && high<=numbers.size()-1){
            if(numbers[low]==numbers[mid]){
                low--;
            }
            if(numbers[high]==numbers[mid]){
                high++;
            }
        }
        int len = high - low + 1;
        if(len>numbers.size()/2) return numbers[mid];
        return 0;
    }*/
    

        // 讨论帖中的做法,个人理解为:假如有某个数字出现次数超过一半,那么它们每个元素有一口气,我累计收集这些气(遍历):
        // 遇到这个元素,气+1;遇到其他元素,气-1;如果气等于0,则更新气味为新元素的气;
        // 最后验证一下这个气是否为所求:因为留下来的气,对应元素出现次数可以少于一半。
    int MoreThanHalfNum_Solution(vector<int> numbers){
        int n = numbers.size();
        if (n == 0) return 0;
        
        int num = numbers[0], count = 1;
        for (int i = 1; i < n; i++){
            if (numbers[i] == num) {
                count++;
            }
            else{
                count--;
            }
            if (count == 0){
                num = numbers[i];
                count = 1;
            }
        }

        //verification
        count = 0;
        for (int i = 0; i < n; i++){
            if (numbers[i] == num){
                count++;
            }
        }
        if (count * 2 > n){
            return num;
        }
        return 0;
    }
};
目录
相关文章
|
存储 Python
海明距离(Hamming Distance)
海明距离(Hamming Distance)是用来衡量两个二进制数之间差异程度的指标,它表示两个二进制数之间最多有多少个比特的差异。海明距离可以用于衡量数据传输或存储中的错误率,以及检测噪声干扰。 海明距离的计算方法是:对于两个 n 位二进制数,将它们进行逐位比较,如果对应位上的数字不同,则计算距离时增加 1。然后将所有位上的距离加在一起,得到海明距离。
2528 1
|
12天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1255 5
|
1天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
11天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1275 87
|
12天前
|
云栖大会
阿里云云栖大会2025年9月24日开启,免费申请大会门票,速度领取~
2025云栖大会将于9月24-26日举行,官网免费预约畅享票,审核后短信通知,持证件入场
1821 13