时间戳

首页 > 解决方案 > 请解释在 1...N 中查找缺失数字的过程

c++ - 请解释在 1...N 中查找缺失数字的过程

问题描述

我们得到一个 n-1 个整数的列表，这些整数在 1 到 n 的范围内。列表中没有重复项。列表中缺少其中一个整数。我们必须找到丢失的号码。这就是问题。

我的方法是对 1...N 中的所有元素和数组的所有元素进行 XOR，然后输出 XOR。它工作正常，但我在 Geeks for Geeks 中找到了另一种解决方案，但我无法理解他们在做什么以及为什么这样做。

方法：我们可以从已知数字中选择一个数字并从给定数字中减去一个数字

代码：

#include <bits/stdc++.h> 
using namespace std; 

// a represents the array 
// n : Number of elements in array a 
int getMissingNo(int a[], int n)  
{  
    int i, total=1;  

for ( i = 2; i<= (n+1); i++) 
{ 
    total+=i; 
    total -= a[i-2]; 
} 
return total;  
}  

//Driver Program 
int main() { 
    int arr[] = {1, 2, 3, 5}; 
    cout<<getMissingNo(arr,sizeof(arr)/sizeof(arr[0])); 
    return 0; 
}

标签： c++algorithmdata-structuresc++17

解决方案

使用求和公式：

从 i = 1 到 N = N * (N + 1) / 2 的总和

https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

添加列表中的数字。从数字的总和中减去这个，你就有了你丢失的数字。

推荐阅读