程序员面试题精选100题(05)-数组中只出现一次的数字[算法]
- 博客分类:
- 笔试面试
题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是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); }
发表评论
-
析构函数为虚函数的原因
2012-09-09 11:42 783我们知道,用C++开发的时候,用来做基类的类的析构函数 ... -
hash的应用
2012-08-31 23:02 921第一部分为一道百度面试题Top K算法的详解;第二部分为关 ... -
微软智力题
2012-08-29 19:59 537第一组1.烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有 ... -
C++不能被继承的类
2012-08-27 20:16 994一个类不能被继承, ... -
括号对齐问题
2012-08-27 10:47 1349解法一:左右括号成一对则抵消 可以 ... -
树的遍历
2012-08-19 10:43 672/****************************** ... -
堆排序
2012-08-16 14:24 841堆:(二叉)堆数据结构是一种数组对象。它可以被视为一棵完全 ... -
多态赋值
2012-08-14 16:16 775#include <iostream> usi ... -
static变量与static函数(转)
2012-08-13 10:15 698一、 static 变量 static变量大致分为三种用法 ... -
不用sizeof判断16位32位
2012-08-10 15:21 1658用C++写个程序,如何判断一个操作系统是16位还是3 ... -
找出连续最长的数字串(百度面试)
2012-08-09 15:15 1108int maxContinuNum(const char*in ... -
顺序栈和链栈
2012-08-06 10:01 763顺序栈:话不多说直接上代码 #include ... -
队列的数组实现和链表实现
2012-08-05 16:20 991话不多少,数组实现上代码: #include<i ... -
KMP算法详解
2012-08-02 21:40 847KMP算法: 是在一个“主文本字符串” ... -
字符串的最长连续重复子串
2012-08-01 15:05 9696两种方法: 循环两次寻找最长的子串: <方法一> ... -
寻找一个字符串连续出现最多的子串的方法(转)
2012-07-31 21:19 914算法描述首先获得后缀数组,然后1.第一行第一个字符a,与第二行 ... -
字符串的循环移位
2012-07-31 16:52 931假设字符串:abcdefg 左循环两位:cdefgab 右 ... -
一次谷歌面试趣事(转)
2012-07-31 15:26 724很多年前我进入硅谷 ... -
约瑟夫环问题(循环链表)
2012-07-30 21:31 1237题目描述:n只猴子要选大王,选举方法如下:所有猴子按 1, ... -
面试之单链表
2012-07-30 20:18 6881、编程实现一个单链表的建立/测长/打印。 ...
相关推荐
程序员面试题100题(63)-数组中三个只出现一次的数字[算法].pdf,这是一份不错的文件
面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现直接插入排序 面试题2:编码实现希尔(Shell)排序 11.2 交换排序 面试题3:编码实现冒泡排序 面试题4:编码实现快速...
异常表示程序运行过程中可能出现的非正常状态,运行时异常表示虚拟机的通常操作中可能遇到的异常,是一种常见运行错误。java编译器要求方法必须声明抛出可能发生的非运行时异常,但是并不要求必须声明抛出未被捕获的...
超级有影响力的Java面试题大全文档 1.抽象: 抽象就是忽略一个主题中与当前目标无关的那些方面,以便更充分地注意与当前目标有关的方面。抽象并不打算了解全部问题,而只是选择其中的一部分,暂时不用部分细节。...
道常见的程序员面试题,这些题目偏向中低难度,是入门上手不错的选择。另外这些题目基本上在各大 OJ 上也都有,可以非常方便地提交自己的实现进行练手。 如果刚开始练习算法题目,「剑指 Offer」是个不错的切入点。...
1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char const*...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
18、一个用户表中有一个积分字段,假如数据库中有100多万个用户,若要在每年第一天凌晨将积分清零,你将考虑什么,你将想什么办法解决? 107 19、一个用户具有多个角色,请查询出该表中具有该用户的所有角色的其他...
1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
不多说了 直接上目录: 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 ...84. C语言惠通面试题 428 85. C语言常用宏定义 450 有需要的朋友可以根据需求下载,内容为WORD格式的,绝对清晰
高级进阶c语言教程 目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
实例032 递归算法的经典面试题 39 实例033 制作一个数字猜猜看小游戏 40 实例034 使用goto语句在数组中搜索指定图书 42 第3章 字符串处理技术 44 3.1 字符及字符串转换 45 实例035 将字母全部转换为大写或小写 45 ...
net的最近面试经典试题ASP.NET面试题集合 1. 简述 private、 protected、 public、 internal 修饰符的访问权限。 答 . private : 私有成员, 在类的内部才可以访问。 protected : 保护成员,该类内部和继承类中...