亦或的应用-继续!:1到n中减少了一个数,顺序被打乱,找出缺失的数

对于丢失一个数的情况: 

1)用1+2+...+n减去当前输入数据的总和。时间复杂度:O(n) 空间复杂度:O(1) 【容易溢出】

2)用12...*n除以当前输入数据的总积。时间复杂度:O(n) 空间复杂度:O(1) 【容易溢出】

3)用1^2^...^n的结果在逐个异或当前输入数据。时间复杂度:O(n) 空间复杂度:O(1)

4)对输入数据排序,然后从头到尾遍历一次。时间复杂度O(nlogn) 空间复杂度O(1)

5) 对输入数据进行Hash,然后从头到尾遍历一次。时间复杂度O(n) 空间复杂度O(n)

原文地址:https://www.cnblogs.com/szhan/p/3280770.html