标题: 讨论:一道经典求重复数题目的一种解法
性别:未知-离线 龙剑止水

Rank: 4
组别 校尉
级别 奋威校尉
好贴 2
功绩 11
帖子 124
编号 99726
注册 2007-1-9


发表于 2008-10-4 22:50 资料 文集 短消息 看全部作者
讨论:一道经典求重复数题目的一种解法

题目很常见:
现在有一个数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数。

应该是N年前的一道面试题,通常的解法应该是快速排序吧。同学找工作,今天在网上看到这个题,用了一个新的方法来做(可能是我孤陋了),我想不明白,所以拿来讨论一下。
解法大致是这样的,把数组Copy一份到数组2,然后把数组2右移一个位置,与原数组对应位置比较,如果相同留下,如果不同踢掉。如此循环,终止条件是剩下一个数字或是动作之后没有踢掉元素。

例如:
2 3 3 3 2 2 3 4 3 2 3
3 3 3 2 2 3 4 3 2 3 2
   3 3    2


3 3 2
3 2 3
3

试了几组数,感觉还挺准,(虽然复杂度不是O(n)),可想了半天想不出为什么。想和大家讨论一下,看看这种解法到底对不对,如果对用到的是什么原理


顶部

正在浏览此帖的会员 - 共 1 人在线




当前时区 GMT+8, 现在时间是 2025-8-27 02:00
京ICP备2023018092号 轩辕春秋 2003-2023 www.xycq.org.cn

Powered by Discuz! 5.0.0 2001-2006 Comsenz Inc.
Processed in 0.008477 second(s), 9 queries , Gzip enabled

清除 Cookies - 联系我们 - 轩辕春秋 - Archiver - WAP