![更多课程](/zhuzhan/img/btn-course.png)
![选择中心](/zhuzhan/img/btn-center.png)
![logo](/zhuzhan/img/logo.png)
C/C++培训
达内IT学院
400-111-8989
![](/zhuzhan/images/weixin.jpg)
大家好,昨天和同事聊到了一个比较有意思的C语言面试题,感觉还不错,拿出来与大家分享一下,记得在以前的推文中我们写过此类问题,此题确实较为经典,我们也对它进行了一定的变形总结推广,希望对大家有所帮助,请看题:
题目是这样的:在一个整数数组中1个数出现了3次,其余的数都出现了2次,请找出出现3次的数。建议大家自己先思考一下,我们下面直接给出了解法。
一、三种常规解法:
①用两个循环,外层循环每次提供一个数,内层循环遍历数组进行比对,用另外的变量存储相等的次数,内层循环结束之后,如果存储次数的变量等于3,就输出这个元素,然后退出,否则外层循环提供下一个值,继续上述过程。
for(i=0;i<SIZE;i++)
{
n=0;
for(j=0;j<SIZE;j++)
if(src[i]==src[j])
n++;
if (n==3)
{
printf("%d\n",src[i]);
return;
}
}
②建立一个临时数组,初始化为0,遍历一遍题目所给数组,将数组对应的值记录到新数组中,出现一次就++,所给数组的值和新数组的下标一一对应,然后遍历新数组,读出记录的值。
for(i=0;i<SIZE_src;i++)
tmp[src[i]]++; //临时数组tmp
for(i=0;i<SIZE_tmp;i++)
if (tmp[i]==3)
{
printf("%d\n",i);//打印下标
return;
}
③先用快排排序,再遍历数组,如果第i个数组元素与第i+1个相同就i+2,如果i与i+1,i+2都相同,就输出,否则继续下一轮循环。
for(i=0;i<SIZE;i+=2) {
if(src[i]==src[i+1]){
if(src[i]==src[i+2]) {
printf("%d\n",i);
return;}}}
以上3种方法无疑都是可行的,但都不是最优解,有的时间复杂度有问题,有的无法估计边界,有的代码太复杂,也不是我们今天想讲的。其实本题采用位运算中异或是最简单的。
讲之前要明确几个知识点:
(1)整数与0异或为本身。与本身异或为0,即本身的奇数次异或还为本身,偶数次异或为0。
(2)异或运算符合结合律和交换律。有了以上两点,本题很简单了,全部异或后,出现2次数的异或都为0,只剩出现3次的数了。
int singlenumber(int src[], int size)
{
int result=0;
for(int i=0; i<size; i++)
result ^= src[i]; //遍历数组全部异或
return result;
}
当你还在担心能否就业时,达内学员提前被企业录取;当你转辗于各大招聘会时,达内学员收到了高薪offer;当你在各大招聘网站投递简历时,达内学员中有人一毕业进入五百强名企。所以选择很重要。找C++培训班,选达内就对了。
版权声明:转载文章来自公开网络,版权归作者本人所有,推送文章除非无法确认,我们都会注明作者和来源。如果出处有误或侵犯到原作者权益,请与我们联系删除或授权事宜。
填写下面表单即可预约申请免费试听!怕钱不够?可就业挣钱后再付学费! 怕学不会?助教全程陪读,随时解惑!担心就业?一地学习,可全国推荐就业!