c++数据结构与算法题目快速找出机器故障



c++数据结构与算法题目快速找出机器故障。

题目来自编程之美

题目 1：假设一个机器只存储一个标号为ID的记录，假设每份数据保存2个备份，这样就有2个机器存储了相同的数据。其中ID是小于10亿的整数，在某个时间，如果得到一个数据文件ID的列表。是否能够快速的找到这个表中仅出现一次的ID?即快速找出出现故障的机器存储的数据ID。

分析：具体参考点击打开链接

代码

 

[cpp] view plaincopy


  1. #include <iostream>
  2. #include <assert.h>
  3. using namespace std;
  5. /*函数nArr中的只有一个元素出现一次，其他元素都是出现两次*/
  6. int Find(int nArr[],int nLen)
  7. {
  8.     assert(nArr != NULL && nLen > 0 && nLen % 2 == 1);
  9.     int nNum = 0;
  10.     for (int i = 0;i < nLen;i++)
  11.     {
  12.         nNum ^= nArr[i];
  13.     }
  14.     return nNum;
  15. }
  17. int main()
  18. {
  19.     int nArr[9];
  20.     for (int i = 0;i < 9;i++)
  21.     {
  22.         cin>>nArr[i];
  23.     }
  24.     cout<<Find(nArr,9)<<endl;
  25.     system(“pause”);
  26.     return 1;

题目 2： 假设一个机器只存储一个标号为ID的记录，假设每份数据保存2个备份，这样就有2个机器存储了相同的数据。其中ID是小于10亿的整数，如果有两台机器死机呢？（假设同一个数据的俩个备份不会同时丢失，即列表中缺少的是两个不等的ID）

 

分析：具体参考点击打开链接

代码：

  1. #include <iostream>
  2. #include <assert.h>
  3. using namespace std;
  5. int FindLastOne(int nNum)
  6. {
  7.     assert(nNum > 0);
  8.     int nPos = 1;
  9.     int nLast = nNum & 1;
  10.     while (0 == nLast)
  11.     {
  12.         nPos++;
  13.         nNum >>= 1;
  14.         nLast = nNum & 1;
  15.     }
  16.     return nPos;
  17. }
  19. /*判断nNum的nPos位置上是否为1*/
  20. bool IsSameBit(int nNum,int nPos)
  21. {
  22.     assert(nPos >= 0);
  23.     return nNum & (1 << (nPos - 1)) ? true : false;
  24. }
  26. /*函数nArr中有两个元素都出现一次，其他元素都是出现两次*/
  27. void Find(int nArr[],int nLen)
  28. {
  29.     assert(nArr != NULL && nLen > 0);
  30.     int nNum = 0;
  31.     int nPos = 0;
  32.     int nNumFirst = 0;
  33.     int nNumSec = 0;
  34.     //首先把所有元素都异或一遍
  35.     for (int i = 0;i < nLen;i++)
  36.     {
  37.         nNum ^= nArr[i];
  38.     }
  39.     /*根据最后异或的结果中1的位置，把数据分两组，并分别在每组进行异或*/
  40.     nPos = FindLastOne(nNum);
  41.     for (int i = 0;i < nLen;i++)
  42.     {
  43.         if (IsSameBit(nArr[i],nPos)) //nArr[i]在nPos位置为1
  44.         {
  45.             nNumFirst ^= nArr[i];
  46.         }
  47.         else  //nArr[i]在nPos位置为0
  48.         {
  49.             nNumSec ^= nArr[i];
  50.         }
  51.     }
  52.     cout<<”Losing Num: ”<<nNumFirst<<” ”<<nNumSec<<endl;
  53. }
  57. int main()
  58. {
  59.     int nArr[8] = {1,2,3,1,2,4,5,4};
  60.     Find(nArr,8);
  61.     system(“pause”);
  62.     return 1;
  63. }