快速找出机器故障 - 编程之美1.5
Also check http://www.xuebuyuan.com/1014709.html
问题1、已知一个数组,数组中只有一个数据是出现一遍的,其他数据都是出现两遍,我们要把这个数据找出来
方法三、利用异或运算(推荐使用)
思想:将列表中的所有ID异或,之后得到的值即为所求ID。
利用异或运算可以得到
X^X=0 X^Y=Z X^0=X
- 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
- 最终的结果仍然是那个只出现一次的数
缺点:前提是只有一个ID出现一次,若出现多次,则不适合
方法四、利用 "不变量" (推荐使用)
利用数学中“不变量”的概念,例如预先保存所有ID之和与所有ID之积。
对于两台机器死机的话,就可以列出如下方程:
x+y=a
xy=b
不过实现上可能会有问题,就是大整数乘法造成算术溢出,可以尝试通过采用平方和来解决。
时间复杂度:O(N)时间,空间复杂度O(1)
问题2、已知一个数组,数组中有两个不同的数据都出现一遍,其他数据都是出现两遍,我们要把这两个数据找出来
题里面是丢失的是两个不同的数据,我们这里两种情况都考虑下
如果缺少的两个数字不相同,
方法:进行异或操作
思路:由于缺少的数不同,则最后异或的结果不为0。
- (1)对数组中所有的ID进行异或,结果为a
- (2)我们找到a的二进制表示中,最低一位为1的位置b
- (3)根据b位是否为1,将ID数组中的数分为两个数组,其中一个数组中的b位为1,另一个队列中的b位为0。
- (注意,每个数组中,除了那个只出现一次的数外,其他数都是出现两次的,此时就可以在数组内使用异或操作)
- (4)然后对两个数组,分别进行异或操作,则将得到两个不为0的数字。即为所丢失的两个ID。
问题1: 找出出现奇数次的两个数
http://bylijinnan.iteye.com/blog/1573337
http://bylijinnan.iteye.com/blog/1573337
void findRepeatedTwoNumbers(int a[], int n, int& no1, int& no2) { int i, j, temp; //计算这两个数的异或结果, temp = 0; for (i = 0; i < n; i++) { temp ^= a[i]; } // temp的值现为两个出现奇数次的数的异或 // 找第一个为1的位 for (j = 0; j < sizeof(int) * 8; j++) { if (((temp >> j) & 1) == 1) { break; } } // 第j位为1,说明这两个数字在第j位上是不相同的 // 由此分组即可,一个分组在此位上为1,另一组在此位上为0;这两个数分别位于这两个分组中; // 对两个分组中的数分别计算异或,得到的值即为所求的值; 每个分组中除所求的数外,其余的都出现偶数次; no1 = 0, no2 = 0; for (i = 0; i < n; i++) { if (((a[i] >> j) & 1) == 0) // 分组1 { no1 ^= a[i]; } else // 分组2 { no2 ^= a[i]; } } }
如果缺少的两个数字相同
(此时数组中所有ID都是成对出现,异或值还是为0,不能使用异或实现)
方法:可以使用不变量实现。丢失两个,生成两个方程,联立求值
此时我们采取的方法如下:
- (1)首先计算出初始未丢失之前,所有ID之和。
- (2)然后计算出丢失之后的ID之和,然后(1)(2)结果进行相减操作,得到方程x+ y = a。
- (3)利用丢失前后平方和之差,来与(2)进行联立,得到方程x * x + y * y = b。
- (4)对两方程进行联立,即可以求出最终的结果。
问题3、已知一个数组,数组丢失了三个数据,我们要把这三个数据找出来
之后可以扩展到N个
方法一:我们需要建立三/N个方程,求出这些都是的数
此时,当方程为N时,要求N个方程可不好求
方法二:使用计数排序 + 计数值达到A时Map不在存储
这时,最终可以得到这几个数
给你一副杂乱的扑克牌(不包括大小王),任意从其中抽出一张牌,怎样用最简单的方法来知道抽出的是1~13中的那一张?(不要求知道花色)
方法:利用不变量
事先算好所有牌的和(1+...+13) x 4 = 364
然后分别减去留下的牌点数,最终得到的就是抽出的那一张
Also check http://www.xuebuyuan.com/1014709.html