[LeetCode]Single Number 异或的妙用
2024-08-31 08:10:36
1、数组中仅仅有一个元素仅仅出现一次,其余出现偶数次。
利用异或中同样元素相互抵消的方式求解。
2、数组中仅仅有2个元素仅仅出现一次。其余出现偶数次。
class Solution {
public:
int singleNumber(int A[], int n) {//返回仅仅出现一次的元素
if(n==1)return A[0];
int i,sum=A[0];
for(i=1;i<n;++i)sum^=A[i];
return sum;
}
vector<int> twoSingleNumber(int A[], int n) {
int res=singleNumber(A,n);//找出全部元素异或的结果,即两个目标元素异或的结果
int pos=0,i;
while(res){//找出res为1的一位(这是两个目标元素位数不同的一位),从而可将A划分为两部分,这两部分中,同样的数字为在同一部分,由于他们每位都同样
if(res&1)break;
res>>=1;
pos++;
}
vector<int>ans(2,0);
for(i=0;i<n;++i){
if((A[i]>>pos)&1)ans[0]^=A[i];//假设是pos位为1。即为第一部分,对这部分进行异或,终于同样的数字消除掉,得到的就是第一个元素
else ans[1]^=A[i];
}
cout<<ans[0]<<" "<<ans[1]<<endl;
return ans;
}
};
最新文章
- Html和CSS布局技巧
- JS学习笔记01
- 深入理解CSS定位中的偏移
- 探索 OpenStack 之(16):计量模块 Ceilometer 介绍及优化
- Extjs 4.2 Grid增删改及后台交互(Java)
- 第三百三十五天 how can I 坚持
- 常用加密算法的Java实现(一) ——单向加密算法MD5和SHA
- PHP的curl常用的5种写法
- android脚步---数字时钟和模拟时钟
- C++中的输入参考
- 【2017-06-05】Jquery.ajax
- vue2.0的瀑布流组件-使用说明
- JVM 指令
- 在Eclipse中调用Algs4库
- EXCEL文件导入时报_未在本地计算机上注册Microsoft.ACE.OLEDB.12.0提供程序
- Fox And Dinner CodeForces - 510E (最大流)
- ISO27001适用性-导图
- mysql jdbc操作
- 10.29 scrum meeting newbe软件团队工作分配
- phantomjs-prebuilt@2.1.16 install: `node install.js`
热门文章
- 如何使用 Open Live Writer 插入原图
- linux下mysql 查看默认端口号与修改端口号方法
- 【BZOJ4487】【JSOI2015】染色问题
- 2015 Multi-University Training Contest 2 Friends
- [MySQL]快速解决";is marked as crashed and should be repaired";故障[转]
- 在android中,编译的项目使用到第三方jar的导入方法 终极版!
- 在独立的文件里定义WPF资源
- 【甘道夫】Sqoop1.99.3基础操作--导入Oracle的数据到HDFS
- ORA-06553:PLS-306:wrong number or types of arguments in call to &;#39;&;#39;
- xcode5. 安装cocos2d-x 学习中。。。