博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
求数组中只出现一次的数字(算法)
阅读量:7067 次
发布时间:2019-06-28

本文共 1110 字,大约阅读时间需要 3 分钟。

  首先,我们先考虑简单的情况下,就是只有一个出现一次的数字,其余数字都出现2次,这样我们可以采用一种很巧妙的方法:“异或”。

void findNumAppearOnce(int date[],int length,int &num){       if(length<2)              return;        num=0;        for(int i=0;i

 然后,我们考虑有两个出现一次的数字的情况。同理,我们依然采用上面的方法,由于两个出现一次的数字肯定不相同,最后的结果就是这两个数字的异或结果,因而这个结果必不为0,至少存在一位为1(就是由于这两个出现一次的数字的同一位上:一个为0,一个为1)。因此,我们首先找到一位不为0的二进制位n,把所有的数据按照此位划分为两组,这两组的第n位分别为0和1,这样就能保证每组中必然包含一个仅出现一次的数字。

  源代码参考:剑指Offer

  代码如下:

#include 
using namespace std;//从左向右移动,获取第一个为1的位数unsigned int FindFirstBitIs1(int num){ int indexBit = 0; while(((num&1)==0)&&(indexBit<32)) { num=num>>1; ++indexBit; } return indexBit;}//对数据分组bool IsBit1(int num,unsigned int indexBit){ //移动相应的位数,让相对位置移动到最后一位上 num=num>>indexBit; //例如:1001101 ^ 0000001 这样的情况为0 ; 1010110 ^ 0000001 这样的情况为1 return (num & 1);}void findNumAppearOnce(int date[],int length,int &num1, int &num2){ if (length<2) return; //get num1^num2 int resultExclusiveOR = 0; for (int i=0;i
>a[i]; int num1,num2; findNumAppearOnce(a,6,num1,num2); cout<<"num1="<
<

 

 

转载地址:http://bqtll.baihongyu.com/

你可能感兴趣的文章
获取GET/POST提交的数据,并处理中文问题
查看>>
jdbc 获取connection 对象的三种方式
查看>>
jsp标签+jstl
查看>>
第二阶段个人总结09
查看>>
FATAL ERROR: Could not find ./bin/my_print_defaults的解决办法
查看>>
文摘《十一》
查看>>
jquery 笔记。。。——》摘自武方博
查看>>
一个夭折,
查看>>
C#开发微信门户及应用(1)--开始使用微信接口(转)
查看>>
Kali-linux使用社会工程学工具包(SET)
查看>>
ScriptManager(脚本控制器)
查看>>
Android chromium 2
查看>>
poj_3468,线段树成段更新
查看>>
什么是mybatis?
查看>>
【算法导论】学习笔记——第6章 堆排序
查看>>
NS3编译运行
查看>>
Python+Appium自动化环境搭建
查看>>
wap网站seo如何优化呢?
查看>>
Java基础-Date类常用方法介绍
查看>>
js 属性getset
查看>>