101道经典面试题 - 03

03.Given an array of size N in which every number between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like.

  译：给你一个长度为N的整数数组，这个数组的元素值都在1到N之间，请判断数组中是否有重复的元素。

73 个解决方案

#1

这个简单，求和，看是否等于(1+n)n/2

#2

兄台可能没注意到 1+3 = 2+2 这样的简单算式，所以加和的想法固然好，但是不奏效；
容易想到的肯定是排序了，基数排序要求很严格，当然效率也最高，该题条件恰好符合这样苛刻的条件，所以应用一下这个思想就可以了；

  简单描述一下：
  一遍扫描数组，遇到ai ！= i的元素时，将ai换到 数组的ai位置，将那个位置的元素换到与其值相同的位置，直到遇到 i，换成一个有序的数组前缀或遇到重复的元素退出。

  代码：
  int FindDup()
{
    int num[11] = {0,1,3,2,5,4,8,6,2,6,9};
int tmp = 0;
for (int i=1; i<11; i++)
{
if( i != num[i] )
{
tmp = num[num[i]];
if( tmp == num[i])
return 1;
num[num[i]]=num[i];
num[i]=tmp;
i--;
}
}
return 0;
}

#3

for(i=0;i<n-1;i++)
 for(j=i+1;j<n;j++)
 if(a[i]==a[j])   有重复的元素

#4

int repeat(int *list,int len)
{
  int i,current;
  for(i=0;i<len;i++)
  {
    if(listi[i]<0)
      current=-list[i]-1;
    else
      current=list[i]-1;
    if(list[current]<0)
      return 1;
    list[current]=-list[current];
  }
  return 0;
}

#5

搂住的答案真不错，一次循环就搞定了！学习了！

#6

lfclfclfc()  穷举没错；
 
  hl_md_wj() 的方法好像行不通，请细心的帮我看看这个数组用hl_md_wj() 的方法能不能通过：a[0] = 5, a[1] = 1, a[2] =2, a[3]=3, a[4]=4, a[5]= 5;

#7

int repeat(int *list,int len)
{
  byte * temp = new byte[len];
  memset( temp, 0, sizeof(byte)*len);
  for(int i =0; i < len; i++)
  {
     if(temp[list[i]-1] != 0)
      temp[list[i]-1] = 1;
    else
      return list[i];
  }
 delete temp;
 return 0;
}

#8

#include <stdio.h>
int repeat(int *list,int len)
{
    int i,current;
    for(i=0;i<len;i++)
    {
        if(list[i]<0)
            current=-list[i]-1;
        else
            current=list[i]-1;
        if(list[current]<0)
            return 1;
        list[current]=-list[current];
    }
    return 0;
}
int main()
{
  int list[]={5,1,2,3,4,5};
  printf("%d\n",repeat(list,6));
  return 0;
}
程序运行结果
1

#9

china_cooooooooooder的算法快不。..

#10

我认为二楼的答案是正确的
楼主：兄台可能没注意到 1+3 = 2+2 这样的简单算式，所以加和的想法固然好，但是不奏效；
｛1,3｝是不可能的只可能是{1,2}
题目所谓N 长数组，只放 1-N的数，如果全放整数，且不重复，那和就是1+2+..+N,二楼正确
如果不全放整数，楼主在3楼写的代码就是错误的

#11

楼上的兄弟，1+2+3=2+2+2，这个呢

#12

是我搞错了

#13

#define N 10
int FindDup()
{int a[N]={0,1,2,3,4,5,6,7,8,2};
 int b[N]={0};
 int i=0;
 while(i<N && b[a[i]]==0)
 {
    b[a[i]] = 1;
    i++;
 }
 return i>=N ? 0:1;
}

#14

大家来看一下了，我想这个是不是可以求平方和，这样不就可以了！大家认为如何。。。。

#15

int sum = 0;
for(int i = 0; i < n; ++i)
{
    sum += i;
}
int sum2 = n*(n-1)/2;
return sum2 - sum;

#16

写错，是
for(int i = 1; i <= n; ++i)
{
    sum += i;
}

#17

Dim n As Integer
Dim FindDup() As Integer
ReDim FindDup(n)
Dim a,b As Integer
For a = 0 to n
   For b = 0 to n
      If FindDup(a)=FindDup(b) And a<>b Then
         Return True
         Exit Sub
      End If
   Next
Next

#18

另设一个数组，存储某数是否出现过的信息：

// 如果有重复的数，则返回改数，否则返回-1
int IsDuplicate(int *arr, int N)
{
    bool *exist = new bool[N+1];
    ZeroMemory(exist, N+1);
    for(int i=0; i<N; ++i)
    {
        if(!exist[arr[i]])
            exist[arr[i]] = true;
        else
        {
            delete []exist;
            return arr[i];
        }
    }
    delete []exist;
    return -1;
}

#19

另设一个数组，存储某数是否出现过的信息:建棵树把,如果N太大的话效率会很低的

#20

to t12s88() 
不可以：
a^2+b^2=c^2+d^2
==>(a-c)(a+c)=(d-b)(d+b)

suppose:
a=51 c=49
b=23 d=27
can not distinct

#21

为啥我运行楼主的程序，会有运行时错误？

#22

楼主用这一组数据试试：
int num[11] = {1,5,3,2,10,4,8,6,11,7,9};

#23

int a[10] = {1,5,5,8,7,5,9,5,7,1};
for (int k = 0; k <10; k++)
{
for (int j = 10 ; j>k;j-- )
{
if (a[k]==a[j])
{
cout << "same!"<< endl;
exit(0);
}
}
}

#24

时间O(1.5N)，空间O(N)

#25

1：构造长度为N的桶t；
2：遍历数组a，如果a[i] = k，则t[i]++；
3：遍历桶，若t[i] <> 1，则表示有重复的元素；
4：如果不存在i，使得t[i] <> 1，则数组a中没有重复的元素。

时间O(1.5N)，空间O(N)

#26

1：构造长度为N的桶t；
2：遍历数组a，如果a[i] = k，则t[i]++；若t[i] > 1则表示有重复的元素

时间O(N)，空间O(N)

#27

可以用方差
1,2...n
的方差是最大的

#28

搞错了，方差不是最大
但不知道可不可以用方差来判断

#29

#include <stdio.h>

int Isright(int a[],int n)
{
int differ, aver,square,standard;

square=aver=0;
for(int i=0;i<n;i++)
{
aver+=a[i];
square+=a[i]*a[i];
}
differ=n*square-aver*aver;
standard=n*n*(n+1)*(n-1)/12;
printf("%d\t%d\n",differ,standard);
if(standard==differ)
return 1;
else
return 0;
}
void main()
{
int a[100],n;

printf("input n:");
scanf("%d",&n);
printf("input a[i]:");
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
printf("%d\n",Isright(a,n));
}

#30

mark

#31

前面的china_cooooooooooder()介绍的算法应该是无错的，不过编程时变更了题意而已
int FindDup()
{
int num[11] = {0,1,3,2,5,4,8,6,2,6,9,10};
int tmp = 0;
for (int i=1; i<11; i++)
{
if( i != num[i] )
{
tmp = num[num[i]];
if( tmp == num[i])
return 1;
num[num[i]]=num[i];
num[i]=tmp;
i--;
}
}
return 0;
}
----
注意，判断应该是从num[1]开始的到num[N]结束，而不是从num[0]开始，也就是说测试用例定义时，应该定义的数组是a[N+1],其中a[0]=0是预定义的，且后续元素不出现0。
另外我受gz80()和t12s88() 启示，在想是否可以同时检测和以及平方和，甚至立方和，如果不同时满足应该的值，那就有重复的，当然，这个的前提是测试用例都落在那个范围内的。不知道那位能从数学上证明这个方法是可行的。

#32

用一个字典变量，往里面加，如果报错就说明有重复了

#33

关注

#34

我觉得只要数组元素的和不等于1+2+3+.....+n那就是有重复的元素了，是不是？

#35

int arr[n];
BOOL Is()
{
BOOL bRet = TRUE;
DWORD dwF = 0x000000000000000000000000000000;
for ( int i = 0 ; i < n ; i++ )
{
if ( dwF & arr[i] )
{
bRet = FALSE;
break;
}
dwF = dwf | arr[i];
}
return bRet;
}
-----------------------------------------------------------
伪代码，仅仅发表一下个人想法

#36

学习ing......

#37

Top    cjq87() ( ) 信誉：100    Blog 
bool is()
{if (sum(array[n])!=sum(0~N))
return 1;
elseif (sum_2(arrsy[n])!=sum_2(0~N))
return 1;
return 0;}
sum  为数组的和
sun_2 为数组的平方和


 

#38

支持二楼，换位置排序的算法应该最优了

#39

前面的错了，用|和&进行操作有限制的，呵呵，任意数的二进制来进行余和或的操作不对
另写了一种方法
int arr[n];

{
    BYTE byFlag[n];
    memset( byFlag, FALSE, MSP_MAX_ADDRESS );

   for ( int i = 1; i <= n; i++ )
   {
       if ( byFlag[arr[i]] == TRUE )
       {
           return FALSE;
       }
       byFlag[arr[i]] = TRUE;
   }

   return TRUE;
}

#40

楼主的方法不错，我也想到了交换，但是没有想透。
另外，楼主的方法可不是传统意义的1重循环，因为循环里有i--，实际上，写成2重循环更合适。

#41

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool if_dumplicated(const vector<int>& v);

int main(void)
{
    vector<int> vec;
    vec.push_back(3);
    vec.push_back(1);
    vec.push_back(4);
    vec.push_back(5);
    vec.push_back(2);
    vec.push_back(2);

    cout << boolalpha << if_dumplicated(vec) << endl;

    return 0;
}

bool if_dumplicated(const vector<int>& v)
{
    vector<int> vec(v);
    for (int i = 0; i < vec.size(); ++i)
    {
        while (vec[i] != i)
        {
            if (vec[i] == vec[vec[i]])
            {
                return true;
            }
            swap(vec[i], vec[vec[i]]);
        }
    }
    return false;
}

#42

遍历一次数组 ，计算总和Sum ,如果 Sum 不等于 N * (N + 1)/2 ,那么数组含有重复元素 ； 否则不重复 。

因为如果数组长度为N ,那么其中的元素值是不能大于N的， 比如N = 3, 那么元素只能取1或者2或者3 ； 当且仅当各个元素都不重复，那么Sum的值才等于1+2+3+....+N

#43

我来发一个答案。

#44

大家可以参考快速排序的方法，任取一个值，比他小的放在左边，比他大的放在右边，相等则返回。然后迭代去做左边的数和右边的数。时间复杂度在o（nlogn）。呵呵。大家给个意见。

#45

用两个for语句就for(i=1;i<=n;i++)//判断1到n 是那个重复的
              for(j=0;j<n;j++)
              if(i==N[j]) return 1;

            return 0;


   这是我的的传统方法的思路和。。 我的数学不好呀。。

#46

这倒题目的实质是，能否在时间复杂性o(n)和空间复杂o(1)的情况下完成，否则完全没有讨论的意义，mark下

#47

学习，不太懂

#48

荐2楼

#49

楼主好算法！

#50

二楼的算法比较理解，顶一下！