资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

数组中出现次数超过一半的数字(C++剑指Offer详解)-创新互联

数组中出现次数超过一半的数字(C++剑指Offer详解)
第一次见到这个题,感觉简单到爆,不就是sort函数排个序,取中位数,遍历一遍计个数不就OK了吗?但是面试时,sort可能会让你自己去实现,或者说,题目要求:不能修改输入的数组呢???
第一种方法(基于Partition函数)
注意:此方法修改了输入的数组

创新互联公司:从2013年创立为各行业开拓出企业自己的“网站建设”服务,为上千余家公司企业提供了专业的成都做网站、成都网站建设、网页设计和网站推广服务, 按需定制由设计师亲自精心设计,设计的效果完全按照客户的要求,并适当的提出合理的建议,拥有的视觉效果,策划师分析客户的同行竞争对手,根据客户的实际情况给出合理的网站构架,制作客户同行业具有领先地位的。

核心:出现次数超过一半的数字,排序后中位数肯定是这个数字

解题思路:通过Partition函数,随机选出数组中的一个元素(我的代码中默认是数组中第一个元素),并且通过快排的思想,小的元素移到随机值前面,大的元素移到随机值的后面,然后返回随机值最后的位置。然后通过调用Partition函数,用返回的index值和中值判等,如果index>mid,说明中位数在左边,end=mid-1,如果index

class Solution {
public:
    int MoreThanHalfNum_Solution(vector numbers)
    {
        int length = numbers.size();
        if (length <= 0)//判空
            return 0;
        int start = 0;
        int end = length - 1;
        int index = Partition(numbers, start, end);//Partition函数随机值在数组中的位置
        int mid = length >> 1;//统计学的中位数
        while (index != mid)//随机值与中位数位置的判等
        {
            if (index>mid)
            {
                end = index - 1;
                index = Partition(numbers, start, end);
            }
            else if (index num, int start, int end)
    {
        int index = start;
        int sum = num[start];//默认随机值为首位,这里可以用“随机函数”
        //从第二位开始
        for (int i = start + 1; i num, int result)
    {
        int count = 0;
        for (int i = 0; inum.size())
            return true;
        return false;
    }
};

第二种方法(计数法)
注意:此方法没有修改输入的数组

核心:出现次数超过一半的数字个数比其他所有数字个数至少多一

解题思路:从首位开始(result==numbers[0]),遇到相等的元素,count++,遇到不相等的元素,count--,当count==0时,result重新赋值为当前元素,重新给count赋值为1,直到数组遍历完之后,返回result

疑惑???既然,判断出来了,为什么还要调用Check函数,因为我们无法判断result是否为出现次数最多的元素,就算是出现次数最多的元素,不知是否超过数组一半,例如:{5,5,5,5,5,3,3,3,4,4,4,4} {3,3,3,4,4,4,4,5,5,5,5,5}

class Solution {
public:
    int MoreThanHalfNum_Solution(vector numbers) {
        if(numbers.size()<=0)
            return 0;
        int result=numbers[0];
        int i=1;
        int count=1;
        for(;i num,int result)
    {
        int count=0;
        for(int i=0;inum.size())
            return true;
        return false;
    }

另外有需要云服务器可以了解下创新互联cdcxhl.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


网页标题:数组中出现次数超过一半的数字(C++剑指Offer详解)-创新互联
文章源于:http://www.cdkjz.cn/article/djjeci.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220