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


	青木风亮 (枯木)


	定远侯谏议大夫

组别	翰林学士
级别	平西将军
好贴	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 编辑 ]

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