编程之美 1.5 快速找出故障机器 - 服务器托管|北京服务器租用|机房托管租用|IDC托管租用|机房机柜带宽租用-价格及费用咨询

题意：

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

问题1、在某个时间，如果得到一个数据文件ID的列表。

是否能够快速的找到这个表中仅出现一次的ID?即快速找出出现故障的机器存储的数据ID。

问题2、如果有两台机器死机呢？（假设同一个数据的俩个备份不会同时丢失，

即列表中缺少的是两个不等的ID）

扩展题、如果所有的机子都有三个备份，也就是说同一ID的机子有三台。

而且同时又有三台机子死机，还能用上面的方法解决吗？

如果有N台备份，又同时有N台机器死机呢？

相关问题、给你一副杂乱的扑克牌(不包括大小王），任意从其中抽出一张牌，

怎样用最简单的方法来知道抽出的是1~13中的那一张？(不要求知道花色）

解法一：

对于列表中的每一个ID，遍历列表查找是否存在相同的ID，利用数组记录每个ID出现的次数，

遍历完，次数小于2的就是要找的；

时间复杂度为O(N)，空间复杂度为O(N)。空间复杂度在N很大时不理想。

解法二：

利用hash表。遍历列表，对于每一个ID，先检查hash表中是否有与之相同的ID，

若有，则从Hash表中删除该ID；否则，将该ID加入到hash表中。

这样，遍历完列表后，hash表中剩下的那一个元素即为所求ID。

时间复杂度为O(N)，空间复杂度在最好的情况下为O(1)，在最坏的情况下为O(N)。

解法三：

利用异或运算，因为所以ID出现2次，只有一个出现一次，而a^a=0，

所以将这个列表中的所有ID异或后的值即为所求ID。

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

若是有2个ID仅出现一次，设为A和B，那么所有ID的异或值为A^B，无法确定A与B的值；

但是仍然可以找到，若A=B，A^B=0，则可以通过求和的方法A=B=（所有ID和-所以正常工作ID和）/2

若A!=B，A^B！=0，那么这个值最高为1，显然A与B当中有且只有一个数的相同位为1；

所以根据这一位，我们可以将a和b分开，并将数分成两组。

我们在结果数字中找到第一个为1的位的位置，记为第N位。

现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组，

第一个子数组中每个数字的第N位都为1，第二个子数组的每个数字的第N位都为0。

所以把第N位为1的异或结果num1，把第N位为1的异或结果num1，

#include
using namespace std;

void FindTwoDifferentNum(int a[],int n,int &num1,int &num2)
//返回数组a中两个只出现一次的数字num1和num2
{
  int i,ans=0,k;

  for(i=0;i    ans^=a[i];
  
  num1=ans;//保存ans 
  
  k=0;//k表示的是第N位 a和b的不同 
  while((ans&1)==0)
  {
    ans>>=1;
    k++;
  }

  ans=num1;
  for(i=0;i  {
    if((a[i]>>count)&1)
      num1^=a[i];
  }
  num2=num1^ans;//num1和全部异或的结果异或，就是num2
}

int main()
{
  int a[]={1,5,3,4,2,3,1,5,4,6};
  int num1, num2;
  FindTwoDifferentNum(a,sizeof(a)/sizeof(int),num1,num2);
  cout}

解法四：

利用“不变量”。所有ID的和为一个不变量，对剩下ID求和。

所有ID的和与剩下ID的和之差即为所求ID。

由于所有ID之和可以事先算好，所以，该方法也可以在O(N)时间，O(1)空间内解决。

问题2，用2个方程解决

首先计算出初始未丢失之前，所有ID之和。

然后计算出丢失之后的ID之和，然后(1)(2)结果进行相减操作，得到方程x+ y = a。

利用丢失前后平方和之差，来与（2）进行联立，得到方程x*x+y*y=b。

对两方程进行联立，即可以求出最终的结果。

五、扩展问题

如果同时有A个备份，同时有B台机器发生故障，怎么解决？

在B小于4的情况下，还可以考虑采用解法四构造方程解决。但是，B超过4的情况下，方程势必很复杂，建议采用解法三，当然，解法三需要改进。需要对存入Hash表的ID计数，当计数值达到A时再将这个ID从hash表中删除。

六、相关问题

给你一副杂乱的扑克牌(不包括大小王），任意从其中抽出一张牌，

怎样用最简单的方法来知道抽出的是1~13中的那一张？(不要求知道花色）？

直接采用解法四；首先算好所有牌的和(1+…+13)x4=364，然后分别减去留下的牌点数，就得到抽出的是哪一张。

题意：