查找序列中缺少的数字

我给出了一个n个整数的列表，这些整数的范围是1到n。列表中没有重复项，但列表中缺少其中一个整数。我必须找到缺失的整数。查找序列中缺少的数字

Example: If n=8 
I/P [7,2,6,5,3,1,8] 
O/P 4 

I am using a simple concept to find the missing number which is to get the 
sum of numbers 
     total = n*(n+1)/2 
And then Subtract all the numbers from sum.

但是，如果数字的总和超出了最大允许的整数，上述方法将失败。

所以我搜索的第二溶液，我发现一种方法如下：

1) XOR all the elements present in arr[], let the result of XOR be R1. 
2) XOR all numbers from 1 to n, let XOR be R2. 
3) XOR of R1 and R2 gives the missing number.

这是如何工作的方法。如何是R1的异或和R2发现在上述情况下丢失的整数？

来源

2013-08-20 poorvankBhatia

暴力强制它如何？对数组进行排序，检查'[n - （n-1）]'不等于1的索引对。 – Renan

为什么会有最大允许的整数？ – VoronoiPotato

@VoronoiPotato：如果序列中有10亿个数字并且他仅限于32位整数，该怎么办？ –

要回答你的问题，你只需要记住，

A XOR B = C => C XOR A = B

，并紧跟在

(PARTIAL SUM) XOR (MISSING ELEMENT) = (TOTAL) => 
(TOTAL) XOR (PATIAL SUM) = (MISSING ELEMNT)

为了证明第一个属性，只写下来XOR真值表：

A B | A XOR B 
0 0 | 0 
0 1 | 1 
1 0 | 1 
1 1 | 0

真值表：如果两个位相同，则XOR的结果为假，真o therwise。

在一个不相关的注释中，XOR的这个属性使它成为简单（但不是微不足道的）加密形式的很好候选。

来源

2013-08-20 13:05:53 Save

首先，即使存在整数溢出（只要n适合于int），也可以使原始方法正常工作。

至于异或方法，请注意R1 xor M == R2（其中M是缺少的数字）。由此可见，R1 xor M xor R2 == 0因此是M == R1 xor R2。

来源

2013-08-20 13:04:49 NPE

XOR的作品，因为每次你XOR有点1你翻转它，每次你XOR一点点0它保持不变。因此，所有数据的结果保存了缺失的数字，这给您带来了所有数字的“负面”印象。 XOR这两个一起恢复你丢失的号码。

来源

2013-08-20 13:05:33

让我们看看低位（LOB）的XOR，以保持简单。令x是缺少的整数。

列表中的每个整数都有助于R1或LOB（LOB（R1））的1或0。

范围中的每个整数对LOB（R2）贡献1或0。

现在假设LOB（R1）== LOB（R2）。由于R2 == R2 XOR x，只有在LOB（x）== 0 == LOB（R1）异或LOB（R2）时才会发生这种情况。（1 xor 1 = 0,0 xor 0 = 0）

或者假设（LOB（R1）== LOB（R2））这只有在LOB（x）== 1 == LOB（R1）XOR LOB（R2）（1 xor 0 = 1,0 xor 1 = 1）

但是，对于所有这些位来说，低位位适用，因为XOR是逐位计算的。

来源

2013-08-20 13:11:48

查找序列中缺少的数字

回答

相关问题