C程序查找数字序列中缺失的整数

Question

给你一个由 n-1 个不同的正整数组成的序列，所有正整数都小于或等于整数“n”。您必须找到范围 [1,2,...,n] 中缺少的整数。不使用数组解决问题。

输入格式：一行包含整数“n”，其中 2<=n<=10,000 第一行之后是一系列“n-1”个不同的正整数。请注意，序列可能没有任何特定顺序。

我使用数组获取代码

#include<stdio.h>
int main()
{
 int i,j,n[9999],m,t;
 scanf("%d",&m);
 for(i=1;i<m;i++)
  {
   scanf("%d",&n[i]);
  }
 for(i=1;i<m;i++)
  {
   for(j=1;j<i;j++)
    {
      if(n[j]>n[j+1])
       {
         t=n[j];
         n[j]=n[j+1];
         n[j+1]=t;
        }
    }
   }
   for(i=2;i<m;i++)
    {
     if(n[i-1]!=n[i]-1)
       {
          printf("%d",n[i]-1);
          break;
       }
  }
 return(0);
 }

如何在不使用数组的情况下实现同样的效果？

Answer 1

逻辑很简单。您只需找到给定 n 的系列连续数字的总和。

然后，现在将问题中提供的所有这些数字相加，以准确找到给定数字的总和。

不同之处在于您可以说这两个总和之间的差值是缺失的数字。

例如：- 假设 n = 6。

所以，你只求从1,...,6开始的n个连续整数之和为：- 6 * (6+1) / 2 = 21。从1开始的n个连续整数之和的公式是 {n * (n+1)} / 2。

然后，现在求出给定 n-1 个数字的总和。

比如说，给出的数字是 1,2,4,5,6。那么他们的总和 = 1 + 2 + 4 + 5 + 6 = 18.

因此，缺失数=连续n个数之和-给定（n-1）个数之和=3。

Answer 2

求出给定整数的总和。从 n(n+1)/2 中减去它。

解释：前n个整数之和为n(n+1)/2。因此给定整数的总和+缺失的整数= n(n+1)/2.

假设n=10;

那么，1+2+3+4+5+6+7+8+9+10=10*(10+1)/2==55

如果给定的整数是 - 1,2,3,4,5,6,7,8,10。

那么答案=55 - (1+2+3+4+5+6+7+8+10)=9.

Answer 3

要在 1 到 n-1 的数组中找到缺失的数字，我们有两种方法，一种是求和公式，另一种是使用 XOR 方法，两者都给出 O(n) 时间复杂度。

使用求和公式

1 求数字之和

   total = n*(n+1)/2

2 从总和中减去所有数字，然后你会得到丢失的号码。

使用异或方法

1 对所有数组元素进行异或，令异或的结果为X1。

2 XOR 所有从 1 到 n 的数字，令 XOR 为 X2。

3 X1 和 X2 的 XOR 给出缺失的数字。

Answer 4

'您可以使用 sum 方法作为数组中总数的总和，例如总数组大小 = 5，元素为 1,2,4,5,6 然后大小 = 5 然后使用此方法 (n(n+ 1))/2 这里 n=5 所以 15 是通过计算得出的数组元素的总和 1+2+4+5+6 =18 因此 18-15=3 简单'

C程序查找数字序列中缺失的整数

C program to find missing integer in a sequence of numbers

c

arrays

sequence