找出数组中重复的数 - 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
浏览: 1033128 次
来自: 北京
标示对java很陌生！
Java中\是转意字符， 可是你的这句话我没看懂，只要把得到的 ...
可以参考最新的文档：如何在eclipse jee中检出项目并转 ...
，非常好。如题所述，这类问题出现的频率太高了，有必要进行归纳归纳~
---&给定一个长度为N的数组，其中每个元素的取值范围都是1到N。判断数组中是否有重复的数字。（原数组不必保留）
方法1.对数组进行排序（快速，堆），然后比较相邻的元素是否相同。时间复杂度为O(nlogn)，空间复杂度为O(1)。方法2.使用bitmap方法。定义长度为N/8的char数组，每个bit表示对应数字是否出现过。遍历数组，使用 bitmap对数字是否出现进行统计。时间复杂度为O(n)，空间复杂度为O(n)。方法3.遍历数组，假设第 i 个位置的数字为 j ，则通过交换将 j 换到下标为 j 的位置上。直到所有数字都出现在自己对应的下标处，或发生了冲突。时间复杂度为O(n)，空间复杂度为O(1)。
示例代码：
class Solution {
// Parameters:
an array of integers
the length of array numbers
duplication: (Output) the duplicated number in the array number
// Return value:
true if the input is valid, and there are some duplications in the array number
otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
//思路：遍历数组，假设第 i 个位置的数字为 j ，则通过交换将 j 换到下标为 j 的位置上。
//直到所有数字都出现在自己对应的下标处，或发生了冲突。
//ps：由于长度为n的数组里的所有数字都在0到n-1的范围内，所以不需要扩展额外的空间
for(int i=0;i&i++){
if(numbers[i]!=i){
if(numbers[i]!=numbers[numbers[i]])
swap(numbers[i],numbers[numbers[i]]);
*duplication=numbers[i];
阅读(...) 评论()> 怎么判断数组中是否存在重复的值
怎么判断数组中是否存在重复的值
yangsy & &
发布时间： & &
浏览：17 & &
回复：1 & &
悬赏：0.0希赛币
如何判断数组中是否存在重复的值？如何判断数组中是否存在重复的值？举个例，数组中保存数据是部门代号,如下：(数据不只这么多)EP400EP000EP400EP401EP402重复的值是EP400(也有可能是其它值重复),出现的位置可能是数组中任一位置如何在oracle ebs 11i form buidlerk中判断数组中存在重复的值　　　　　　
--参考:for i in unt loop
for j in (i+1unt loop
if v_arr(i)=v_arr(j) then
dbms_output.put_line(v_arr(i));yangt180 & &
20:04:51 & &
& & （0）（0）引用
本问题标题：
本问题地址：
温馨提示：本问答中心的任何言论仅代表发言者个人的观点，与希赛网立场无关。请对您的言论负责，遵守中华人民共和国有关法律、法规。如果您的言论违反希赛网问答中心的规则，将会被删除。
暂无合适的专家
&&&&&&&&&&&&&&&
希赛网 版权所有 & &&maolv11 的BLOG
用户名：maolv11
文章数：89
访问量：2455
注册日期：
阅读量：5863
阅读量：12276
阅读量：412009
阅读量：1100095
51CTO推荐博文
650) this.width=650;" src="http://img.my.csdn.net/uploads//_1182.JPG" alt="">本文出自 “” 博客，请务必保留此出处
了这篇文章
类别：未分类┆阅读(0)┆评论(0)Ruby如何判断一个数组中是否有重复元素？ · Ruby China
请问 要Ruby去判断一个数组中是否有重复元素（只要知道是否有重复，不需要知道具体有哪些重复），最简单高效的写法是什么？
我现在能给出的写法只有判断 array.size & array.uniq.size ，虽然看上去很简单，但是不够高效，请问大家还有什么更好的建议嘛？
你测试过 array.size & array.uniq.size 的性能么？
uniq 是很慢，但很难写出一个更高效简单的。
不一定简单的方法肯定是有的，比方说取所有元素放 Hash 里再判断大小。但性能上的改善微乎其微。
坐等达人出高性能算法 -^
OK 我想出一个在一般情况下能提高一定量级的方法：
module DuplicationChecker
set = Hash.new
each do |e|
return false if set[e]
set[e] = e
set.size & size
Array.class_eval do
include DuplicationChecker
当数组元素比较多且有不少重复时，可以在遇到第一个重复元素时结果判断提高速度。大致猜想如果重复元素很少（比方说100万大的数组中只有一两个重复，我猜会慢到跟直接 uniq 差不多）。
弄个 hash 一个个往里塞…… 遇到塞过的就是有重复的了…… 不知道快慢……
遍历一次是最快的，遇到重复马上break.
实际遍历的时间不到一次。
比如有1万条记录，遍历到第20条时遇到重复了，马上break .
感觉uniq需要遍历所有元素的。
但是写起来顺手和执行效率之间不一定冲突。
如果原数组可以改, 判断 a.uniq! 返回值是否为 nil 就可以了
我看过javascript就是这么做。javascript那个是弄个object。据说效率是最高的，问题也有遇到非字符串的很蛋疼了。例如1,2,3,4,5这样
你是说纯数字的 array 么？也一样执行的哇
哇，原来这里的返回值还有差别
Great! 就这个了!
这个有side effect，不推荐这么写。
a.dup.uniq!
于是越来越慢了……
不要紧啊 其实调用这个方法的数组是先经过map方法处理过的，本来就可以被修改的
我说错了吗？
这里的 ～呵呵～ 是表示赞同的微笑 ：）
array.to_enum.uniq!, to_enum 方法为一个数组创建了一个不可变的代理对象, 不知道性能比 dup 是不是好点.
enumerator没有uniq！方法
试了一下你的方法，速度真的不错
我自己也用sort方法试了一下，不过有时快有时慢，速度不是很稳定，有谁知道原因吗？
require 'benchmark'
module DuplicationChecker
set = Hash.new
each do |e|
return false if set[e]
set[e] = e
set.size & size
Array.class_eval do
include DuplicationChecker
arr = 100000.times.inject([]) do |arr, i|
arr && rand(000000)
arr && arr[-1]
Benchmark.bm do |x|
x.report('uniq') do
puts arr.size & arr.uniq.size
x.report('sort') do
arr.sort do |a, b|
eql = (a &=& b)
if eql == 0
x.report('uniq?') do
puts arr.uniq?
x.report('dup') do
puts arr.size & arr.dup.uniq!.size
68-a8-6d-43-46-cc:ruby can$ ruby benchmark.rb
0.080000 (
0.040000 (
uniq?false
0.090000 (
0.110000 (
貌似你是对的.
能说下具体的用例么？ 如果是数据量不大，不值得纠结；如果数据量很大，感觉总有更好的解决渠道，而不是把大数组加进内存来判断
这个算法时间复杂度是O(N)，时间不稳定是因为有时运气好比较靠前，有时运气差。
但是平摊下来趋于稳定。
如knwang说的，小数组无所谓，性能没什么区别，个人认为用有side effect的函数是很不好的practice。
如果是很大数据量的话，这个应用场景还是很多的，比如文字的dedupe，像twitter搜索结果里要去掉重复的内容（其实有点不一样，每个retweet都有少部分不同的内容）。一个简单的做法是计算文字的min hash，然后可以放到map reduce中去去重。
没有很大的量其实 传进来的都是些参数而已 在实际使用过程中我确定决定不会超过5个 之所以提出来只是为了找出更美观的代码（自己定义方法绝对是没有必要的，太麻烦） 效率还是其次的 uniq!应该完全满足要求了。
之所以没更早的说出来不过是抛砖引玉而已，我自己也可以多多学习下：）
如果数组里面都是数字的话 这样会好点吗？tmp = []
array.each do |i|
tmp[i] = 'true'
array.size & tmp.compact .size
array.size & array.to_set.size
我不太知道to_set 的内部实现，是否比 uniq高，但是to_set 应该没有uniq里面的sort方法
后方可回复, 如果你还没有账号请点击这里 。
共收到 26 条回复