| 面试题：找出数组中只出现一次的2个数（异或的巧妙应用）（出现3次） | 您所在的位置：网站首页 › 一次两次的次字怎么写 › 面试题：找出数组中只出现一次的2个数（异或的巧妙应用）（出现3次） |
|
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 分析：这是一道很新颖的关于位运算的面试题。 首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。 这个题目的突破口在哪里？题目为什么要强调有一个数字出现一次，其他的出现两次？我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现依次的数字，因为那些出现两次的数字全部在异或中抵消掉了。 有了上面简单问题的解决方案之后，我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办法就是分别求出这两个只出现一次的数字了。 我们还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为1的位的位置，记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。 现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。因此到此为止，所有的问题我们都已经解决。 基于上述思路，我们不难写出如下代码： /////////////////////////////////////////////////////////////////////// // Find two numbers which only appear once in an array // Input: data - an array contains two number appearing exactly once, // while others appearing exactly twice // length - the length of data // Output: num1 - the first number appearing once in data // num2 - the second number appearing once in data /////////////////////////////////////////////////////////////////////// void FindNumsAppearOnce(int data[], int length, int &num1, int &num2) { if (length < 2) return; // get num1 ^ num2 int resultExclusiveOR = 0; for (int i = 0; i < length; ++ i) resultExclusiveOR ^= data[i]; // get index of the first bit, which is 1 in resultExclusiveOR unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR); num1 = num2 = 0; for (int j = 0; j < length; ++ j) { // divide the numbers in data into two groups, // the indexOf1 bit of numbers in the first group is 1, // while in the second group is 0 if(IsBit1(data[j], indexOf1)) num1 ^= data[j]; else num2 ^= data[j]; } } /////////////////////////////////////////////////////////////////////// // Find the index of first bit which is 1 in num (assuming not 0) /////////////////////////////////////////////////////////////////////// unsigned int FindFirstBitIs1(int num) { int indexBit = 0; while (((num & 1) == 0) && (indexBit < 32)) { num = num >> 1; ++ indexBit; } return indexBit; } /////////////////////////////////////////////////////////////////////// // Is the indexBit bit of num 1? /////////////////////////////////////////////////////////////////////// bool IsBit1(int num, unsigned int indexBit) { num = num >> indexBit; return (num & 1); }示例： 01 10 11 11 100 100 异或结果：11 分组： 01 11 11 异或num1=01 10 100 100 异或num2=10. 成功找到num1和num2. 求最低位1： int get_first_bit(int num){ return num&~(num - 1);}
求一个数最低位1的个数还有多种方法（编程之美提到过）。 参考：剑指offerhttp://zhedahht.blog.163.com/blog/static/2541117420071128950682/ 相似题:
题目为：给你1-1000个连续自然数，然后从中随机去掉两个，再打乱顺序，要求只遍历一次，求出被去掉的两个数。 （基本跟上面的题一样） 解法1：使用异或。 说说异或的两个特性：顺序无关 / 对一个数异或两次等于没有异或。顺序无关就是说异或的元素可以随意交换顺序，而不会影响结果。异或两次可以理解为+x和-x。
首先，这两个数组(打乱前和打乱后)各自异或，也就是1^2^…^1000，得到两个异或值。再对这两个异或值进行一次异或，这样就得到了x^y的指(重复部分互相抵消了)。 获取计算出的异或值的1所在的位置，并继续异或因为x和y是两个不同的整数，所以这两个数的异或结果，转化为二进制的话，一定在某位是1，假设在第3位。也就是说如果把原始数组按第3位是否为0进行划分，就可以分成两个数组，每个数组各包含一个被抽取的数。如果打乱后的数组也按这个规则划分为两个数组，这样就得到了4个数组，其中两组是第3位为0，另外两组是第3位为1。把第3位为0的两个数组所有元素进行异或就能得到被抽取的一个数，同理也就能获得另外一个被抽取的数，于是问题解决。 举例：4个数: 01 10 11 100 我们假设去掉01和10.异或结果为11.按第0为是否为0. 01 11 10 100 11 100 把左边的异或得到01 右边的得到10，问题解决。 另一种方法：用方程求解。 m = ( 1 + 2 + ...+ 1000) - (998 个的和) x + y n = ( 1 * 2 * .... * 1000) / ( 998 个的积)x * y 经公式计算： x = sqart( pow( m , 2 ) / 4 - n ) + m /2 y = m - x
代码测试： double x = 3 ; double y = 39 ; double m = x + y ; double n = x * y ; x = Math.sqrt( m * m / 4d - n ) + m / 2 ; y = m - x ; System.out.println( x ); System.out.println( y ); 另一道相似的题: 找数字分析 原题 数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法，找到x。 分析乍一看这个题目，不少同学立马给出了答案：异或。但举个例子，就会发现，异或是行不通的，一般的方法是利用异或的的如下特性： A xor A = 0 A xor 0 = A 但是这个题目中，数字都是奇数个的，直接采用之前类似题目的异或方法，已经不合适了。 除此之外，我们还可能想到如下的方法： 采用hashmap，时间复杂度O(n)，空间复杂度O(n) 对数组A进行排序，然后在遍历一次，时间复杂度O(nlogn)，空间复杂度O(1) 这个方法还可以。 是否还有一些效果更好的方法呢？这一类的题目，即使简单的异或不能解决，也可以从二进制位、位操作方面去考虑，总之这样的大方向是不会错的。 题目中，如果数组中的元素都是三个三个出现的，那么从二进制表示的角度，每个位上的1加起来，应该可以整除3。如果有一个数x只出现一次，会是什么情况呢？ 如果某个特定位上的1加起来，可以被3整除，说明对应x的那位是0，因为如果是1，不可能被3整除 如果某个特定位上的1加起来，不可以被3整除，说明对应x的那位是1 根据上面的描述，我们可以开辟一个大小为32的数组，第0个元素表示，A中所有元素的二进制表示的最低位的和，依次类推。最后，再转换为十进制数即可。这里要说明的是，用一个大小为32的整数数组表示，同样空间是O(1)的。 程序实现: #include using namespace std; void set(int& a,int i) { a |= (1 |
| CopyRight 2018-2019 实验室设备网 版权所有 |