查找数组中出现两次的数字

Question

我必须编写一个程序，让用户输入一个数字 n，然后在 n+1 范围内输入 n+1 个数字1, n]，其中恰好有一个数字出现不止一次。程序returns多次出现的数字

因此，例如，如果输入是这样的：

然后 n = 3，输入的其余部分是 [1,3] 范围内的四个数字，输出是 2（因为这是多次出现的数字）。

不允许我使用矢量。

我以为我可以这样做:

#include <stdio.h>

int main(){
    int i,n,nr,x,num,aux,k;
    scanf("%d", &n);
    nr = 0;
    for (i=0; i < n+1; i++)
    {
        scanf("%d", &num);
        nr = nr * 10 + num; 
    }
    k=1;
    while(k!=2){
        aux=nr%10;
        nr=nr/10;
        x=nr;
        while (x>0){
            x=x/2;
            if (aux==x%10){
                printf("Numarul este %d", aux);
                k=2;
                break;
            }
        }
    }
    return 0;
}

但这只适用于一位数字，因为我要乘以 10。如果我想支持更大的数字，我可以乘以更大的数字，但是 nr 变得太大了。

那么：如何支持大于 10 的数字？

Answer 1

您需要一个用户指定大小的数组并填充它：

int n;
scanf("%d", &n);
int a[n];

for (i=0; i < n; i++)
{
    scanf("%d", &a[n]);
}

现在您需要遍历数组：

取第一个元素
检查以下所有元素是否存在
如果是，你就完成了
如果没有，取下一个元素，等等。

因为这听起来像是作业，所以我不给你这个循环。用C写应该很容易。

Answer 2

我明白我应该怎么做了。从一开始就很简单，但想起来却很困难。如果我必须在 [1, n] 区间内输入数字，并且有 n+1 个数字，则它们的总和为 n(n+1)/2 + 重复的数字。 “随机”这个词扼杀了我的大脑。重复的数字（按照我老师的要求只有一个）等于求和，你在读数字的时候循环做，然后从1到n减去数字的和。谢谢大家的回复，如果我的回答不清楚，这里是代码。

#include <stdio.h>
int main(){
    int i, n, sum, nr, rep, k;
    k=0;
    sum=0;
    scanf("%d", &n);
    for (i=0; i<=n; i++){
        scanf("%d", &nr);
        if (nr>n){
            k=1;
            break;
        }
        sum = sum + nr;
    }
    if (k==1){
        printf("Introduceti doar numere in intervalul 1, %d \n", n);
    } else{
    rep = sum - (n*(n+1))/2;
    printf("Numarul %d se repeta\n", rep);
    }
    return 0;
}

Answer 3

您可以在 O(n) 内完成此操作而无需额外的 space 或计数器。您可以将访问次数修改为负数。遍历时如果number为负数，则为重复数

 void returnDuplicate(int[] arr)
 {
   int n = arr.length;
   for(int i=0;i<n;i++)
   {
    if(arr[arr[i]-1]>0)
    {
      arr[arr[i]-1]= -arr[arr[i]-1];
    }
    else 
    {
     print arr[i];
     return;
    }
  }
}

在你的例子中，如果i=0，通过反转符号使该元素为已访问；

arr[arr[0]-1] = -arr[arr[0]-1];

arr[0]=-1;

if i = 1, arr[1] =-2;

if i = 2 , arr[2]=-3;

if i = 3 , arr[arr[3]-1] which will be arr[2] which is  already negative, so this the duplicate element

查找数组中出现两次的数字

Find a number that occurs twice in an array

c

arrays

repeat