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

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

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


第一题:给两个变量a和b,如何不使用第三个变量,而交换a和b的值?

第二题:假设给一个长度为2n+1的数组,数组中有n个数是成对出现的,求只出现一次的数的值。要求尽量降低时间和空间复杂度。

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

第一题:这个题很多人应该不会陌生,有同学会说我们可以通过简单的"+"运算就能达到目的:

a = a + b;
b = a - b;
a = a - b;

通过上面的式子,我们可以达到交换两个数的目的。但是,这样是不是就足够了呢?我们需要考虑个问题,如果a和b相加后溢出了怎么办?
谢@tanghao指正,这里溢出也不会有什么问题

因为可能会出现溢出,所以我们就不能使用上面的方法。这时,我们可能就会想到位操作,想到异或(xor)操作,让我们试试可不可以用xor来实现交换:

a = a ^ b;
b = a ^ b;
a = a ^ b;

我们知道,两个相等的数异或后的结果是0,而0异或任何数都等于那个数本身。所以我们发现,通过上面的式子,我们完全可以将两个数交换而不存在溢出的问题。

第二题: 下面我们来看第二题。

按照正常的思路,我们会得到如下的算法:

  1. 对数组进行排序
  2. 从头扫描数组,如果a[i]=a[i+1],则继续;如果a[i]!=a[i+1],则返回a[i]; (i = 0, 2, 4, .....; i<=2n)

让我们来看下这个算法的复杂度,开始排序的时间复杂度是O(nlogn), 后来扫描数组的时间复杂度是O(n),空间复杂度为O(1)。

问题解决了,但是,是否还有时间复杂度更低的方法呢?通过上一题的提示,我们又可以想到xor操作,不要忘记,两个相等的数异或后为0,而0异或任何数都等于原数;并且,异或满足交换律,即a^b^c = c^b^a。因此,我们可以尝试下面的方法:

int i;
int temp = 0;
for(i = 0; i&lt;2n+1; i++){
        temp = temp ^ a[i] ; //数组a为给定数组
}
printf("%d", temp);

因为数组a中,有n个数是成对出现的,因此这2n个数异或完后结果是0,0再异或剩下一个数,结果就是我们要求那个不配对儿的数。所以,我们只需要对数组扫描一遍,在O(n)的时间复杂度,O(1)的空间复杂度内便可以完成题目的要求。

anyShare分享到:
          
Tagged with:
 

3 Responses to “优化算法复杂度的技巧-位操作”

  1. tanghao says:

    第1题:溢出了又如何?如果第一行的加法溢出,那么第二行和第三行的减法同样溢出。这是一个类似“负负得正”的过程。我尝试了几个,没有得到不正确的结果。给个反例?

    • sponge says:

      @tanghao 谢兄台指正,当时有点相当然了 呵呵,想了一下,溢出确实没有什么问题,只不过会影响标志位。已经改正

  2. This is exactly what I have been searching for all the time. Do not stop updating this website.

Leave a Reply

Note: Commenter is allowed to use '@User+blank' to automatically notify your reply to other commenter. e.g, if ABC is one of commenter of this post, then write '@ABC '(exclude ') will automatically send your comment to ABC. Using '@all ' to notify all previous commenters. Be sure that the value of User should exactly match with commenter's name (case sensitive).