重复元素问题-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

重复元素问题

2016-06-08 20:59:43 1644 1

一道笔试题,时间复杂度要求O(N)
int数组中有三个元素出现的次数超过元素总个数的1/4,在规定时间复杂度下,求出这三个数。
我的思路,交卷的一刹那,我发现自己考虑非常不全面。
定义三个变量,保存三个数,在定义三个计数器,开始把a[0],a[1],a[2]赋给三个变量(这里有问题,万一重复了),然后对后面的数组扫描,出现相等的计数器加一,不相等计数器减一。

已经通知下午2点面试,晚上再跟大家探讨下,这题其实跟数组中有元素超过数组一半是一类问题吧,可能考虑起来要复杂点。

请用C/C++实现,Java我不熟。

取消 提交回答
全部回答(1)
  • a123456678
    2019-07-17 19:32:44
    void find3(int * ID, int n)
    {
        int candidate[3];
        int nTimes[3] = {0};
        int i;
        for (i = 0; i < n; i++)
        {
            if(nTimes[0] == 0)
            {
                if(ID[i] == candidate[1])
                    nTimes[1]++;
                else if (ID[i] == candidate[2])
                    nTimes[2]++;
                else
                    {
                        candidate[0] = ID[i];
                        nTimes[0]++;
                    }
            }
            else if (nTimes[1] == 0)
            {
                if(ID[i] == candidate[0])
                    nTimes[0]++;
                else if (ID[i] == candidate[2])
                    nTimes[2]++;
                else
                    {
                        candidate[1] = ID[i];
                        nTimes[1]++;
                    }
            }
            else if (nTimes[2] == 0)
            {
                if(ID[i] == candidate[0])
                    nTimes[0]++;
                else if (ID[i] == candidate[1])
                    nTimes[1]++;
                else
                {
                    candidate[2] = ID[i];
                    nTimes[2]++;
                 }
            }
            else
           {
                if(ID[i] == candidate[0])
                    nTimes[0]++;
                else if(ID[i] == candidate[1])
                    nTimes[1]++;
                else if(ID[i] == candidate[2])
                    nTimes[2]++;
                else
                    nTimes[0]--, nTimes[1]--, nTimes[2]--;
            }
        }
    printf("三个水王ID分别是:%d,%d,%d\n", candidate[0], candidate[1], candidate[2]);
    }
    0 0
相关问答

42

回答

[@徐雷frank][¥20]什么是JAVA的平台无关性

大河人家 2018-10-29 23:55:20 147531浏览量 回答数 42

170

回答

惊喜翻倍:免费ECS+免费环境配置~!(ECS免费体验6个月活动3月31日结束)

豆妹 2014-10-29 17:52:21 233945浏览量 回答数 170

8

回答

OceanBase 使用动画(持续更新)

mq4096 2019-02-20 17:16:36 341408浏览量 回答数 8

13

回答

[@饭娱咖啡][¥20]我想知道 Java 关于引用那一块的知识

心意乱 2018-10-31 18:44:12 143662浏览量 回答数 13

119

回答

OSS存储服务-客户端工具

newegg11 2012-05-17 15:37:18 302706浏览量 回答数 119

22

回答

爬虫数据管理【问答合集】

我是管理员 2018-08-10 16:37:41 148997浏览量 回答数 22

24

回答

阿里云开放端口权限

xcxx 2016-07-20 15:03:33 660630浏览量 回答数 24

31

回答

[@倚贤][¥20]刚学完html/css/js的新手学习servlet、jsp需要注意哪些问题?

弗洛伊德6 2018-10-27 21:52:43 148117浏览量 回答数 31

43

回答

【精品问答集锦】Python热门问题

小六码奴 2019-05-30 15:27:34 144680浏览量 回答数 43

10

回答

[@墨玖tao][¥20]为什么流式处理框架都是 java 写成的,JVM 是不是在流和批存在着特殊优势。还有分布式资源调度,感觉Mesos 的成长速度跟不上 Yarn。这是为什么?

管理贝贝 2018-10-23 13:18:03 137784浏览量 回答数 10
+关注
0
文章
14879
问答
问答排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载