如何找到丢失的元素
https://labuladong.gitee.io/algo/4/30/115/
看完这篇文章，你不仅可以学习算法例程，还可以去LeetCode获取以下问题：
28.缺少数字(简单)
———
我在之前的文章中写过几个有趣的智力问题，今天我来讲一个巧妙的话题。
标题很简单：
给定一个长度为n的数组，它的索引应该在[0，n]中，但是现在你必须放入n ^ 1个元素[0，n]，那么一定有一个元素放不下。请找出这个缺失的元素。
这个问题并不难。我们应该很容易想到，如果我们把这个数组按顺序排列，然后再遍历一遍，不是很容易找到丢失的元素吗？
或者，借助数据结构的特点，用一个HashSet把数组中的所有数字都存储起来，然后遍历[0，n]之间的数字，在HashSet中查询，这样就可以很容易地找出丢失的元素。
排序解的时间复杂度为O(NlogN)，而HashSet解的时间复杂度为O(N)，但存储HashSet需要O(N)的空间复杂度。
第三种方法是位操作。
对于异或运算()，我们知道它有一个特殊的性质：一个数与自身的异或运算结果为0，一个数与0的异或运算结果为自身。
而且，异或运算满足交换律和结合律，即：
2 ^ 3 ^ 2=3 ^ (2 ^ 2)=3 ^ 0=3
而这道题可以通过这些性质巧妙地计算出缺失的元素。假设nums=[0，3，1，4]:
为了便于理解，让我们假设索引首先由一位填充，然后每个元素对应于它自己的相等索引：
这样做之后，我们可以发现除了缺少的元素之外，所有的索引和元素都是一对。现在，如果我们找到缺失的索引2，我们将找到缺失的元素。
这个单号怎么找？只要所有的元素和索引都是XOR，对的个数就为零，只剩下这个单一的元素，就达到了我们的目的。
int missingNumber(int[]nums){ 0
int n=nums.length
int RES=0；
//先与新增加的索引异或。
^=河；
//与其他元素和索引异或。
for(int I=0；I n；(一)
^=一世^一世号决议；
返回res
}
因为异或运算满足交换律和结合律，所以总是有可能消除成对的数，留下缺失的元素。
此时，时间复杂度O(N)和空间复杂度O(1)已经达到最优。我们该回家吗？
如果你这样想，就说明我们被算法深深毒害了。随着我们学到的知识越来越多，我们很容易陷入思维定势。其实这个问题有一个特别简单的解决方法：算术数列的求和公式。
题目的意思可以理解为：有一个等差数列0，1，2，…，n，缺了某个数。请找到它。这个数不是和(0，1，n)-sum (nums)？
int missingNumber(int[]nums){ 0
int n=nums.length
//公式：(第一项和最后一项)*项数/2
int expect=(0n)*(n 1)/2；
int sum=0；
适用于(int x : nums)
sum=x；
回报期望和；
你看，这个方案应该是最简单的，但是说实话，我自己也没有想到这个方案，我问了几个老板，他们也没有想到这个最简单的想法。相反，如果你问一个初中生，他可能很快就会想到。
做完这些，我们该回家了吗？
如果你这么认为，那就意味着我们对细节的控制几乎没有完成。用求和公式计算期望时，有没有考虑过整数溢出？如果乘法的结果太大导致溢出，那么结果一定是错的。
我们刚才的想法是相加和相减。为了避免溢出，我们简单地同时进行求和和相减。非常类似于刚才比特运算解决方案的思路，仍然假设nums=[0，3，1，4]，先加一个索引，然后将元素与索引配对：
让我们从每个索引中减去它对应的元素，然后将减法结果相加。那不是缺少的元素吗？
public int missingNumber(int[]nums){ 0
int n=nums.length
int RES=0；
//新补充索引
RES=n-0；
//将剩余索引和元素之间的差异相加。
for(int I=0；I n；(一)
RES=I-nums[I]；
返回res
}
因为加法和减法满足交换律和结合律，所以总是有可能消除对的数量，留下缺失的元素。
至此，这个算法经历了九个波折十八个波折，终于没有坑了。
_____________
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/84592.html