题目:一个数组里,除了三个数是唯一出现的,其余的都出现偶数个,找出这三个数中的任一个。比如数组元素为【1, 2,4,5,6,4,2】,只有1,5,6这三个数字是唯一出现的,我们只需要输出1,5,6中的一个就行。
下面是我的思路:这个数组元素个数一定为奇数,而且那要求的三个数一定不可能每一bit位都相同,所以我们可以找到其中一个bit位不同,可以把那三个数字分出来,而且可以很推出三个数肯定可以分到两组不同的数组里面去,基于这样的思路就可以找出这三个不同的数字。
找到三个数字一个数的第一个bit位(这里是从右到左算)和其它二个不一样的数就行
如1,5,6的二进制分别为0001,0101,0110。因为6的的第一位为0,而其他的为1,用我的程序第一个输出的就是6了。程序如下:
#include <stdio.h>
//得到第i位的二进制
#define isON(n, i) ((n) & 1 << (i))
// Author: 397090770
// E-mail: wyphao.2007@163.com
// 转载请注明出处
void findTheSingleNumber(int *arr, int size){
int tempA = 0, tempB = 0;
int countA = 0, countB = 0;//用来计数用
int i = 0, j = 0;
for(i = 0; i < 32; i++){ //32位平台上,int只有32位
tempA = tempB = countA = countB = 0;
for(j = 0; j < size; j++){//遍历数组
if(isON(arr[j], i)){
tempA ^= arr[j];
countA++;
}else{
tempB ^= arr[j];
countB++;
}
}
if(countA & 0x1){//奇数
if(0 == tempB){
continue;
}else{
printf("%d\n", tempA);//肯定是不同的数字
break;
}
}else{
if(0 == tempA){
continue;
}else{
printf("%d\n", tempB);
break;
}
}
}
}
int main(){
int arr[] = {
/*1, 3, -9, 2, 1, 2, -10*/
1, 2,4,5,6,4,2
};
findTheSingleNumber(arr, sizeof(arr) / sizeof(arr[0]));
return 0;
}
时间复杂度为O(N)。输出为 6。
(如果要全部输出不同的数,方法和上面的类似,这里就不给出了)
哪位大牛还有别的解法吗?
另附:第一大题为求最大子序列。上面那题为第二大题。最后一道题:
分享到:
相关推荐
2017年小米校园招聘笔试题,笔试同学可以下载看下,熟悉下题型
2015校园招聘笔试题大合集,汇集百度、腾讯、阿里等多家大型互联网企业的面试题,非常具有参考价值。 内容包括: 360校园招聘2015届技术类笔试题.pdf 2015阿里巴巴校招研发在线笔试题.pdf 2015阿里校招系统...
2013年小米校园招聘笔试题.docx
2015 小米校园招聘笔试题
回忆版.pdf百度人搜,阿里巴巴,腾讯华为小米搜狗笔试面试八十题.pdf百度校园招聘笔试面试题合集百度校园招聘笔试题web前端2013.pdf百度校园招聘笔试题产品2.pdf百度校园招聘笔试题产品经理2014.pdf百度校园招聘笔试...
2013年华为中兴校园招聘笔试题,2013年华为中兴的笔试题,包括java,C操作系统,数据结构等
小米公司2013年校园招聘笔试题1,面向测试类的!
网易游戏校园招聘笔试题游戏插件研发岗.pdf 网易游戏校园招聘运维开发岗笔试题.pdf 阿里巴巴校招研发在线笔试题.pdf 阿里校招系统工程师笔试题.pdf 360校园招聘届技术类笔试题.pdf 4399游戏校园招聘游戏开发类笔试题...
小米2014春季校园招聘部分笔试题.doc
2015小米校招技术类笔试题.pdf;2015原题,挺难的,好好做
腾讯招聘笔试题合集 阿里巴巴校园招聘笔试面试题合集 1.Google校招真题与面经68页.pdf 1.京东校招真题与面经77页.pdf 1.微软校招真题与面经47页.pdf 1.甲骨文校招真题与面经45页.pdf 1.百度校招真题与面经87页.pdf 1...
2015届中国顶级IT互联网公司校招笔试题,包括届阿里巴巴校招测试开发工程师在线笔试题,小米校招技术类笔试题,360校园招聘届技术类笔试题,阿里巴巴研发工程师,腾讯校园招聘技术类研发笔试题,美团校园招聘研发...
360校园招聘2015届技术类笔试题.pdf 4399游戏2015校园招聘游戏开发类笔试题.pdf 人人网2015研发笔试卷B.pdf 人人网2015研发笔试卷C.pdf 搜狗2015校园招聘研发类笔试题.pdf 百度2015前端研发笔试卷.pdf 百度2015...
2015校园招聘笔试题大合集。 包含百度、阿里巴巴、腾讯、360、网易、小米、京东、美团、人人等。
阿里、百度、小米、360等各大网络公司校园招聘笔试题汇总PDF版
2014校园招聘嵌入式软件工程师面试笔试题总结,包括2013年秋季校园招聘数码视讯、飞思卡尔、MTK、阿尔科特朗讯、大唐电信、Marvell、展讯、小米、格科微电子等公司的面试笔试题。
阿里-面试题.doc 阿里腾讯华为小米搜狗笔试面试八十题-5.pdf 阿里DBA面试题.pdf ...百度校园招聘笔试题-WEB前端工程师-电子科技大学.pdf Java架构面试专题(含答案)和学习笔记 整套 RAR 超大全压缩包
十月下旬腾讯,网易游戏,百度最新校园招聘笔试题集锦(第271-330题).pdf 微软、谷歌、百度等公司经典面试100题[第101-170题].pdf 微软等数据结构+算法面试100题全部答案集锦.pdf 微软公司等数据结构+算法面试100...
【2013-2015年迅雷校园招聘】迅雷近年产品经理笔试题汇总.pdf 【2014年百度校园招聘】百度客户端产品设计师___产品经理___一面面经.pdf 【2014年谷歌校园招聘】腾讯产品笔试策划+经验.pdf 【2014腾讯校园招聘】腾讯...