优化算法复杂度的技巧-位操作

On September 29, 2010, in 算法, 笔试面试, by sponge

算法是很巧妙的东西,很多时候你以为你写了一个时间复杂度和空间复杂度最低的算法,但实际上还有更好的方法,让我们来看两个通过位操作优化的小算法。

第一题:给两个变量a和b,如何不使用第三个变量,而交换a和b的值?
第二题:假设给一个长度为2n+1的数组,数组中有n个数是成对出现的,求只出现一次的数的值。要求尽量降低时间和空间复杂度。

第一个题目相对比较简单,第二个题目我觉得大多数人也能给出比较好的答案,大家不妨先思考下再看下面的答案。

Tagged with: