玩蛇网提供最新Python编程技术信息以及Python资源下载!

求个时间复杂度极小的python算法

  1. 有一个无序的数组

  2. 数组元素有99个,是1-100之间的数字无序排列,无重复

  3. 求出少了哪个数字

求一个时间复杂度较小的算法?

可以用亦或来实现,性能更好,而且当有更多的数的时候不用担心溢出。
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,具体原因请看这里

既然已经是无序的那就是线性时间复杂度O(n),想不到更简了。

所有数字球和,看看比5050 少了多少

一看就是位运算的问题了,同意二楼的。

可以生成1-100的一个数组,然后求一下差集

玩蛇网文章,转载请注明出处和文章网址:https://www.iplaypy.com/wenda/wd13738.html

相关文章 Recommend

玩蛇网Python互助QQ群,欢迎加入-->: 106381465 玩蛇网Python新手群
修订日期:2017年05月27日 - 11时23分13秒 发布自玩蛇网

您现在的位置: 玩蛇网首页 > Python问题解答 > 正文内容
我要分享到:

必知PYTHON教程 Must Know PYTHON Tutorials

必知PYTHON模块 Must Know PYTHON Modules