首页 > 代码库 > 数组中只出现一次的数字
数组中只出现一次的数字
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1).
例如:输入{2,7,3,10,3,2,5,5} , 输出 7 和 10 。
大家首先想到的是顺序扫描法,但是这种方法的时间复杂度是O(n2)。接着大家又会考虑用哈希表的方法,但是空间复杂度不是O(1)。
应该怎么做才能即满足时间复杂度是O(n)又满足空间复杂度是O(1)的要求呢?
我们可以想一想“异或”运算的一个性质。任何一个数字异或它自己都是0 , 那么我们依次异或数组中的每一个数字,得到的结果就会是只出现一次的2个数字的异或结果。
因为这两个数字不同,所以异或结果肯定不为0,且能够区分开这两个数字的地方就是异或结果中为1的位。假设异或结果中从右向左数第n位为1,那么我们就可以把原来数组中的数字按照第n位是否为1分为两部分,每一部分就会只包含一个只出现一次的数字,且其他的数字都是成对出现。接下来只要分别对这两个数组求异或,就能找出每部分只出现一次的数字。
具体代码如下:
1 /////////////////数组中只出现一次的数字///////////////////////////////////////////////////////// 2 void FindNumsAppearOnce(int* data, int length) 3 { 4 if (data =http://www.mamicode.com/= NULL || length < 1) 5 { 6 return; 7 } 8 int OR = 0 ; 9 for (int i = 0 ; i < length ; i++)//依次异或数组中的每一个数 10 { 11 OR = OR ^ data[i] ; 12 } 13 int index = 1 ; 14 15 while ((OR & 1) != 1 && (index < 8 * sizeof(int)))//从右向左找到异或结果中第一个为1的位的位置 16 { 17 OR = OR>>1; 18 index++; 19 } 20 int num1 = 0 ; 21 int num2 = 0 ; 22 for (int j = 0 ; j < length ;j++) 23 { 24 int temp = data[j]; 25 temp = temp >> (index - 1) ;//向右移位到index的位置 26 if ((temp & 1) == 1) //判断该位是否为1 27 { 28 num1 = num1 ^ data[j]; 29 } 30 else 31 { 32 num2 = num2 ^ data[j] ; 33 } 34 } 35 cout<<num1<<" "<<num2; 36 37 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。