leetcode 位运算异或
2024-09-05 14:47:43
1. 只出现一次的数字（136）
异或的性质总结：
相异为1，相同为0；
a ^ a = 0;
0 ^ a = a;
如果 a ^ b = c 成立，那么a ^ c = b 与 b ^ c = a 均成立。
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
class Solution {
public int singleNumber(int[] nums) {
int res=0;
for(int num : nums){
res=res ^ num;
}
return res;
}
}
2. 只出现一次的数字（136）
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < 32; i++) { // 确定每一位
int sum = 0;
for (int num : nums) {
sum += (num >> i) & 1; // 统计当前位置有多少个元素
}
ans += (sum % 3) << i; // 还原到第i位
}
return ans;
}
}
3. 只出现一次的数字（260）
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
class Solution {
public int[] singleNumber(int[] nums) {
HashMap<Integer,Integer> map=new HashMap<>();
for(int i:nums){
map.put(i,map.getOrDefault(i,0)+1);
}
int count=0;
int [] res=new int[2];
for(int i:map.keySet()){
if(map.get(i)==1){
res[count++]=i;
}
}
return res;
}
}
最新文章
- 设置surfaceView的背景为透明
- IP地址、子网掩码、网络号、主机号、网络地址、主机地址
- HTML5自学笔记[ 9 ]HTML5实现元素的拖放
- submit和button的区别
- JDBC连接池以及动态SQL处理
- ZOJ1372 POJ 1287 Networking 网络设计 Kruskal算法
- 文档数据库RavenDB-介绍与初体验
- HTML通过事件传递参数到js 二 event
- 关于js的一些基本知识（类,闭包，变量）
- IOS开发中数据持久化的几种方法－－NSUserDefaults
- yii2-验证规则，rules，判断条件
- 14-TypeScript简单工厂模式
- 201671010147 2017年8月27号 初学java的感想
- remote: Incorrect username or password ( access token )
- jsp引入本地图片
- rabbitmq更换数据文件和日志文件的存放位置
- iOS实现pdf文件预览，上下翻页、缩放，读取pdf目录
- JVM-即时编译JIT
- PTA之多项式求值
- 微信小程序 循环列表添加点击事件和样式