讨论：一道经典求重复数题目的一种解法 - 辕门射虎


	龙剑止水

组别	校尉
级别	奋威校尉
好贴	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)），可想了半天想不出为什么。想和大家讨论一下，看看这种解法到底对不对，如果对用到的是什么原理

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	青木风亮 (枯木)


	定远侯谏议大夫

组别	翰林学士
级别	平西将军
好贴	3
功绩	521
帖子	2357
编号	12000
注册	2004-7-18
家族	泡泡营

发表于 2008-10-5 03:55 资料主页文集短消息只看该作者

假设数组共m个数元素a是要找的数 a共出现n次（n>m/2）

设a出现的元素编号是x1 x2...xn
则移位后的位置是(x1-1)(x2-1)...(xn-1)

因为n>m/2 根据抽屉原则至少有一个编号要被选到两次即目标a必然出现在子序列中

一个元素能在子序列中存在当且仅当该元素在原序列中构成两两连续对（头尾视作连续）每个连续对可以提供子序列一个元素

现在证明元素a构成的连续对必然多于子序列长度的1/2，即总连续对数量的1/2,即必然多于其它元素连续对的数量和。

则子序列中a的数量超过1/2，可以进行递归证明a必然出现于孙序列中，...
如果一个序列不是仅由一个数字组成，则必然会踢掉数字进行下一步

所以最后留存的数字必为a,仅剩一个数字或当前序列仅含一个数字为递归边界。

该算法简化为这样一个命题：对于一个元素序列，若某元素的数量超过1/2，则其构成的连续对（首尾视作相连）数量必然超过总连续对数量的1/2

由m个质点组成的环，其周长为m,颜色为a彩段总长超过m/2。颜色a和非a的质点在环上构成彩段，指标
La=∑（颜色a的每个彩段长度-1）=∑颜色a的每个彩段长度-k
Lx=∑（非a的每个彩段长度-1）=∑非a的每个彩段长度-k*

因为环的特性颜色a的彩段数量<=非a的彩段数量设为k<=k* 则La>Lx 故命题得证，算法正确

[ 本帖最后由青木风亮于 2008-10-5 12:52 编辑 ]

[广告] 真诚支持说岳，携手共创辉煌