有一个无序的数组
数组元素有99个，是1-100之间的数字无序排列，无重复
求出少了哪个数字
求一个时间复杂度较小的算法？
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
5
544
收藏
所有数字球和，看看比5050 少了多少
可以用亦或来实现，性能更好，而且当有更多的数的时候不用担心溢出。
1到100，比如少了n
令X=1^2^...^(n-1)^(n+1)^...^100,Y=1^2^...^100,那么Y=X^n
X^Y=X^(X^n)=(X^X)^n=n,所以可以通过求X^Y来求出n
这里Y=100,具体原因请看这里
可以生成1－100的一个数组，然后求一下差集
既然已经是无序的那就是线性时间复杂度O(n)，想不到更简了。
一看就是位运算的问题了，同意二楼的。