首页 > 代码库 > 剑指Offer——面试题40：数组中只出现一次的数字
剑指Offer——面试题40：数组中只出现一次的数字
题目：一个整形数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度为O(n)，空间复杂度为O(1)。
思路：题目要求非常严格，O(n)的时间复杂度，O(1)的空间复杂度。难度不小。参照书上给出的思路，实现了一遍，主要也是弥补位运算方面经验的欠缺。
下面是我的代码，用C++实现：
void FindNumAppareOnce(const int data[], const int length, int * num1, int * num2){ if(data =http://www.mamicode.com/= NULL || length < 2) return;>其中的两个涉及位运算的函数如下：
const int GetFirstBitIs1(int ident){ int num = 0; while((((ident >> num) & 0x1) == 0) && (num < (sizeof(int) * 8))) //Take care of the bit operators! (Of course with parentheses) ++ num; return num;}const bool IsThisBit1(int data, const int pos){ return data & (0x1 << pos); //There will be a warning here.}测试部分：
#include <iostream.h>const int L = 10; int main(){ const int test[L] = {2, 3, 16, 3, 2, 5, 5, 32, 8, 8}; int a, b; FindNumAppareOnce(test, L, &a, &b); cout << a << " " << b << endl; return 0;}问题很特殊，特此记录。暂时不推广，不思考更复杂的情况。
剑指Offer——面试题40：数组中只出现一次的数字
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。