找出数组中重复的数 - javaeye - ITeye技术网站
博客分类：
题目是这样的， 数组是无序的， 可能没有重复的数，但最多只可能有一个重复的数，要求用最快的方法找到是否有重复的数。
乍一想，挺难的，但是其实非常的简单。
解决办法：
数组a[N]，1至N-1这N-1个数存放在a[N]中，其中某个数重复一次。写一个函数，找出被重复的数字。时间复杂度必须为o（N）函数原型：
int do_dup(int a[],int N)
××××××××××××××××××××××××××××××××××
假金条的数学思想
此算法题借鉴了假金条的思想，不过比那个过程简单，存放1至N-1，就相当于依次从各个袋中取出1至N-1个金条，但是有一个是重的，计算这N个数的和将相当于称总重量，减去1至N-1的和（用数学方法求）就可求出来重复的数。总之要充分利用数学知识
const int N = 5;
int a[N]={2,1,3,1,4};
int tmp1 = 0;
int tmp2 = 0;
for (int i=0; i&N; ++i)
tmp1+=(i+1);
tmp2+=a[i];
printf("重复的数:%d\n",N-(tmp1-tmp2));
上述方法求1~N的和，减去数组总和，即为N-x 的差值，x为待找的数
可以优化的是1-N的和不用程序算，数学方法直接算了
可定义一个宏,
#define sum(x)& (x(x+1)/2)
当然乘法操作是比较复杂的，当N较小时加几个数的效率可能更高
××××××××××××××××××××××××××××××××××
标志数组法
申请一个长度为n-1且均为'0'组成的字符串。然后从头遍历a[n]数组，取每个数组元素a[i]的值，将其对应的字符串中的相应位置置1，如果已经置过1的话，那么该数就是重复的数。就是用位图来实现的。
其实，只要数还是0 -- n-1里面的数，那么可以用这样的方法判断所有的重复数的位置和值。
比如这样的一个数组
我们生成一个字符串"000";
然后开始遍历，a[0] = 2;
所以，字符串的第二位为"0",那么我们将其置为"1"
字符串为"010"
重复，字符串为"011",,,,,"111"
然后，判断a[3] = 2 那么 第二位为"1"
所以，a[3]为重复数，并且位置为第4位。
上述map等各方法的思路是一致的，即访问过后做标记，再次访问时即可知道是否重复。如果考虑空间复杂度的话，其空间o（N）
int do_dup(int arr[],int NUM)
&&&&&&& int *arrayflag = malloc(NUM*sizeof(int));
&&&&&&& while(i++&NUM)
&&&&&&& arrayflag[i] =
&&&&&&& for(int i=0; i# i++)
&&&&&&&&&&&&&&& if(arrayflag[arr[i]] &= false)
&&&&&&&&&&&&&&&&&&&&&& arrayflag[arr[i]] &=&&&&&&&&&& // 置出现标志
&&&&&&&&&&&&&&& else
&&&&&&&&&&&&&&&&&&&&&& return& arr[i]; //返回已经出现的值
××××××××××××××××××××××××××××××××××
固定偏移标志法
利用标记法单纯写个O(N)的方法并不难，关键是如何保证两点：
不改变A[]的初始值
函数内不开辟另外的O(N)内存空间.
很明显上述方法申请了O(N)内存空间，当N过大时，性能降低了
因此应利用a[N]本身中值和下标的关系来做标记，处理完成后再清除标记即可
a[N]，里面是1至N-1。原数组a[i]最大是N-1，若a[i]=K在某处出现后，将a[K]加一次N，做标记，当某处a[i]=K再次成立时，查看a[K]即可知道K已经出现过。a[i]在程序中最大也只是N-1+N=2N-1（溢出了怎么办啊？？？），此为一个限制条件
int do_dup(int arr[],int NUM)
int temp=0;
for(int i=0; i# i++)
& if(arr[i]&=NUM)
&&& temp=arr[i]-NUM;&&&&&&&&&&& // 该值重复了，因为曾经加过一次了
&&& temp=arr[i];
& if(arr[temp]&NUM)
&&& arr[temp]+=NUM; //做上标记
&&& printf("有重复");&&&
printf("无重复");
return -1;
上面就是时间复杂度O(N), 空间复杂度O(1)的算法!
××××××××××××××××××××××××××××××××××
符号标志法
上述方法将元素加一个固定的NUM来做标记，可能会造成溢出。下列方法中利用符号位来做标记，因为1~N都为正值，所以就无限制了。基本思想是用int数组的符号位作哈希表。（反正不是unsigned int符号位闲着也是闲着）
bool dup(int array[],int n)
&&&& for(int i=0;i&n;i++)
&&&&&&&& if(array[i]&0) //可以以此作下标去判断其他值
&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&& if(array[array[i]]&0)
&&&&&&&&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& return array[i];//已经被标上负值了，有重复
&&&&&&&&&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&& else
&&&&&&&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& array[array[i]]= －array[array[i]]; //否则标记为负
&&&&&&&&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&&&&& }
&&&&&&&& else // |array[i]|代表的值已经出现过一次了
&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&& if(array[-array[i]]&0)
&&&&&&&&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& return -array[i];//有重复
&&&&&&&&&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&& else
&&&&&&&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& array[-array[i]]=－array[-array[i]];
&&&&&&&&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&&&&& }
&&&&& return -1;//没有重复
//用于修复数组
void restorearray(int array[],int n)
&&&&&&& for(int i=0;i&n;i++)
&&&&&&& if(array[i]&0)array[i]= －array[i];
时间复杂度o（n） 空间复杂度o（1）
不过时间复杂度o（n） 空间复杂度o（1）不只一个重复利用此法也是可以实现的
//附上我修改后的算法
bool do_dup_mal(int arr[], int n, int *pre, int *back)
{
int MAX = -1;
int i = 0;
int sameVal = -1;
assert(pre && back);
*pre = *back = -1;
for (int j=0; j&n; j++)
{
if (arr[j] & MAX) MAX = arr[j];
char *arrayflag = new char[MAX+1] ;
if (NULL == arrayflag)
return -1;
//while(i++ & MAX) arrayflag[i] = '\0';
memset(arrayflag, 0, MAX+1 ); // '\0' == 0
for(i=0; i&n; i++)
{
if(arrayflag[arr[i]] == '\0')
arrayflag[arr[i]] = '\1'; // 置出现标志
else
sameVal = arr[i]; //返回已经出现的值
*back =
}
}
delete[]
if (i & n)
{
for (int j=0; j&n; j++)
{
if (sameVal == arr[j])
{
*pre =
int main(int argc, char *argv[])
{
int prePos = -1, backPos = -1;
int myArry[N];
myArry[0] = 1;
myArry[1] = 23;
myArry[2] = 3;
myArry[3] = 4;
myArry[4] = 5;
myArry[5] = 22;
myArry[6] = 7;
myArry[7] = 8;
myArry[8] = 9;
myArry[9] = 22;
myArry[10] = 12;
if (do_dup_mal(myArry, 11, &prePos, &backPos) )
printf("\nT
浏览: 998060 次
来自: 北京
Java中\是转意字符， 可是你的这句话我没看懂，只要把得到的 ...
可以参考最新的文档：如何在eclipse jee中检出项目并转 ...
，非常好。查看: 3156|回复: 10
如何取文本型数组中重复次数最多的那个文本
阅读权限10
在线时间 小时
结帖率： (1/1)
比如文本数组={“B”,“AB”,“B”,“AB”,“ABCD”,“AB”}，可以看出AB是出现次数最多的，那用代码怎样可以取出这个最多的文本成员呢？谢谢！各位高手帮忙！
帮你做了一下 其实很简单的 当次数一样时 取出最先出现的文本
回答提醒：如果本帖被关闭无法回复，您有更好的答案帮助楼主解决，请发表至
可获得加分喔。友情提醒：本版被采纳的主题可在
帖子申请荣誉值，获得 1点 荣誉值,荣誉值可兑换终身vip用户组哦。快捷通道： →
阅读权限70
在线时间 小时
结帖率： (1/8)
帮你做了一下 其实很简单的 当次数一样时 取出最先出现的文本
19:07 上传
点击文件名下载附件
1.2 KB, 下载次数: 350
您可以选择打赏方式支持他
阅读权限90
在线时间 小时
结帖率： (30/40)
用数组_排序（）。然后取第一个。
您可以选择打赏方式支持他
阅读权限10
在线时间 小时
结帖率： (1/1)
首先谢谢回答！但是问题如果是在不知这个数组的前提下，就不能用数组_排序（）来解决了，比如从网页源码中提取出这种数组，然后自动判断出重复最多的那个文本！求解决？？？
您可以选择打赏方式支持他
阅读权限30
在线时间 小时
结帖率： (5/8)
我看到&&是& & B最多
您可以选择打赏方式支持他
阅读权限30
在线时间 小时
结帖率： (5/8)
取每个成员的出现次数& &在对比
您可以选择打赏方式支持他
阅读权限120
在线时间 小时
签到天数: 15 天结帖率： (27/45)
<font color="#4445691 发表于
我看到&&是& & B最多
看来你是误会楼主了，他是要数组与数组之间对比，并不是单个字符之间的对比
您可以选择打赏方式支持他
阅读权限120
在线时间 小时
签到天数: 15 天结帖率： (27/45)
楼上方法可行，但是效率太低，同楼主一起等高人出现
您可以选择打赏方式支持他
阅读权限90
在线时间 小时
先用数组成员1和其他成员对比，有相同的则加1，重复次数加入到一个新数组里，再用数组成员2和其他成员对比，出现次数再加入第二个数组里，依次类推，都比较个遍，看数组2的第几个数最大，那么原来数组的第几个就出现的次数最多，我写的一个查找重复文件的程序有点类似，你看看，去改改，就能实现你的效果
20:36 上传
点击文件名下载附件
3.4 KB, 下载次数: 147
您可以选择打赏方式支持他
阅读权限10
在线时间 小时
结帖率： (1/1)
谢谢mdzwmyy 与 残荷听雨 的帮助，已经达到我要的效果了！
您可以选择打赏方式支持他
精易论坛 - 有你更精彩 /1
一根筷子容易折，一把筷子难折断，相信团队的力量可以互补很多的不足，精易团队欢迎大家的到来
拒绝任何人以任何形式在本论坛发表与中华人民共和国法律相抵触的言论，本站内容均为会员发表，并不代表精易立场!
揭阳精易科技有限公司申明:我公司所有的培训课程版权归精易所有，任何人以任何方式翻录、盗版、破解本站培训课程，我们必将通过法律途径解决！
公司简介：揭阳市揭东区精易科技有限公司致力于易语言教学培训/易语言学习交流社区的建设与软件开发，多年来为中小企业编写过许许多多各式软件，并把多年积累的开发经验逐步录制成视频课程供学员学习，让学员全面系统化学习易语言编程，少走弯路，减少对相关技术的研究与摸索时间，从而加快了学习进度！
防范网络诈骗，远离网络犯罪
违法和不良信息举报电话，企业QQ： ，邮箱：@
Powered by
粤公网安备 25给定一个大小为n的数组，该数组包含数字的范围在 [0...k-1]， k是一个正整数,k & = n。在这个数组找到重复次数最多的数字。
要求时间复杂度为n，空间复杂度为1，可以使用原数组。
遍历数组，让每个元素作为下标的元素加k，最后谁的&#20540;最大，则它对应的下标就是要求的&#20540;。
遍历数组，每个元素&#20540;作为下标的元素&#43;=k；由于会改变数组后面的&#20540;，而我们还要根据数组本来的&#20540;作为下标呢，所以这里，数组原来的&#20540;=数组现在的&#20540;%k；最后比较哪个元素&#20540;最大，则它的下标就是要求的&#20540;。
注解：为何每次要加k？
原因1：数组的所有&#20540;都小于k，则出现次数最多的元素，以它为下标的元素加k的次数也最多，则其遍历一次后也就会最大。
原因2：由于每次都加的是k。则现在&#20540;=原来&#20540;&#43;m个k；所以数组原来的&#20540;很好求：原来&#20540;=现在&#20540;%k。
下面给出C&#43;&#43;代码：
#include&iostream&
#define LEN(array,len) {len=sizeof(array)/sizeof(array[0]);}
int MaxRepeatingNum(int a[], int k)
int maxcount=0;
LEN(a,length);
int max=a[0];
for(int i=0;i&i++){
a[a[i]%k]+=k;
if(maxcount&a[a[i]%k]){
maxcount=a[a[i]%k];
max=a[i]%k;
int main()
int a[]={3,6,5,4,2,3,6,9,8,1,2,3};
cout&&MaxRepeatingNum(a,10)&&
system(&pause&);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：22678次
排名：千里之外
原创：40篇
(1)(2)(2)(1)(3)(2)(5)(3)(3)(5)(4)(1)(3)(12)