第一章 游戏之乐 快速找出机器故障

题目:假设一个机器只存储一个标号为ID的记录,假设每份数据保存2个备份,这样就有2个机器存储了相同的数据。其中ID是一个整数:

问题1、在某个时间,如果得到一个数据文件ID的列表。是否能够快速的找到这个表中仅出现一次的ID?即快速找出出现故障的机器存储的数据ID。

问题2、如果有两台机器死机呢?(假设同一个数据的两个个备份不会同时丢失,即列表中缺少的是两个不等的ID)


解法一:利用异或运算:将列表中的所有ID异或,之后得到的值即为所求ID

利用异或运算可以得到

 X^X=0   X^Y=Z  X^0=X

举个例子:

    比如说ID为 2 1 2 3 1 要找的ID为3  

     2的二进制为010,1的二进制为001  

     3的二进制为011  则2 ⊕1 = 010⊕001= 011   

     011 ⊕2 = 011⊕010=001=1(2⊕1⊕2 = 1)  

     1⊕3 = 001⊕011=010  010⊕001=011 = 3  

     最终的结果仍然是那个只出现一次的数  

时间复杂度为O(N),空间复杂度为O(1)。在时间和空间上,基本已经达到最优。

缺点:前提是只有一个ID出现一次,若出现多次,则不适合


解法二:利用不变量

思路:这里,所有ID的和为一个不变量,对现在剩下ID求和。所有ID的和与剩下ID的和之差即为所求ID。

时间复杂度:O(N)时间,空间复杂度O(1)

本节课后题目:

给你一副杂乱的扑克牌(不包括大小王),任意从其中抽出一张牌,怎样用最简单的方法来知道抽出的是1~13中的那一张?(不要求知道花色)

方法:利用不变量

事先算好所有牌的和(1+...+13) x 4 = 364

然后分别减去留下的牌点数,最终得到的就是抽出的那一张!


相关内容推荐