查找在数组中出现两次的数字
查找在数组中出现两次的数字
提问于 2018-10-07 23:17:48
我必须编写一个程序，其中用户输入一个数字n，然后输入范围为1，n的n+1数字，其中恰好有一个数字出现多次。该程序返回出现多次的数字。
例如，如果输入是这样的：
3
1
2
3
2然后是n = 3，输入的其余部分是1,3范围内的4个数字，输出是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的数字呢？
回答 2
Stack Overflow用户
回答已采纳
发布于 2018-10-07 23:57:08
我知道我应该怎么做。从乞讨开始，这很简单，但想起来却很难。如果我必须在1，n间隔内输入数字，并且有n+1数字，则它们的和是n(n+1)/2 +重复的数字。“随机”这个词害死了我的大脑。重复的数字(在我老师的要求下只有一个)等于sum，当你读这些数字的时候，你在一个循环中做，然后从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;
}Stack Overflow用户
发布于 2018-10-08 01:21:48
您可以在O(n)中做到这一点，而不需要额外的空间或计数器。您可以将访问数修改为负数。在遍历时，如果数字为负数，则数字重复。
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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52689937
复制相关文章
相似问题