面试宝典-面试题3.1：数组中的重复数字

曾经终败给现在 2022-01-07 15:37 178阅读 0赞

一、题意：一个数组中任意一个重复的数字

二、思路：

1.因为题中给的数字大小范围在0~n-1，因此可以直接用一个数据来记录数字是否重复出现过。时间复杂度为O(n)，空间复杂度也为O(n);

2.先给数组排序，然后依次便利。时间复杂度为O(nlogn);

3.利用下标和对应数字的关系对数组进行重排，这样时间复杂度依然为O(n)，但是空间复杂度为O(1);

三、代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include"iostream"
     2 #include"stdio.h"
     3 #include"string.h"
     4 using namespace std;
     5 
     6 const int MAXN=100000;
     7 
     8 int num[MAXN];
     9 int visited[MAXN];
    10 
    11 int GetRepeat1(int n)
    12 {
    13     int i;
    14     for(i=0;i<n;i++)
    15     {
    16         if(!visited[num[i]])
    17             visited[num[i]]=1;
    18         else
    19             return num[i];
    20     }
    21     return -1;
    22 }
    23 
    24 int GetRepeat2(int n)
    25 {
    26     int i=0,temp;
    27     while(i<n)
    28     {
    29         if(num[i]==i) i++;
    30         else if(num[i]==num[num[i]]) return num[i];
    31         else
    32         {
    33             temp=num[i];
    34             num[i]=num[temp];
    35             num[temp]=temp;
    36         }
    37     }
    38     return -1;
    39 }
    40 
    41 int main()
    42 {
    43     int n;
    44     while(scanf("%d",&n)==1)
    45     {
    46         //可加入判断，判断n是否小于1
    47         for(int i=0;i<n;i++)
    48             cin>>num[i];//可加入判断，判断输入的数是否在0~n-1之间
    49         memset(visited,0,sizeof(visited));
    50         int res=GetRepeat1(n);
    51         if(res!=-1)
    52             cout<<"test for function1-the one of repeat number is: "<<res<<endl;
    53         else
    54             cout<<"no repeat number"<<endl;
    55         res=GetRepeat2(n);
    56         if(res!=-1)
    57             cout<<"test for function2-the one of repeat number is: "<<res<<endl;
    58         else
    59             cout<<"no repeat number"<<endl;
    60     }
    61 }

转载于:https://www.cnblogs.com/acm-jing/p/10349376.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/b34d1753a3e645a9bc8e02491932d111.png