【leetcode79】Single Number III
2024-10-08 20:54:27
题目描述:
给定一个数组,里面只有两个数组,只是出现一次,其余的数字都是出现两次,找出这个两个数字,数组形式输出
原文描述:
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
思路:
考虑使用位运算
-那数组分为两组,每个组只有一个出现一次的数字,单独进行异或处理,考虑用全部异或的方式假设得到异或的结果是A,由于两个数字不同。A肯定有一个位是1,找到那个位,然后用来把这个数组分为两组
- 其中一个组的异或结果是B,输出【B,A ^ B】
代码:
public class Solution {
public int[] singleNumber(int[] nums) {
int xOne = 0;
for (int x : nums) {
xOne ^= x;
}
// 获取第一个位1的索引
int k = 0;
for (k = 0; k < Integer.SIZE; ++ k) {
if (((xOne >>> k) & 1) == 1) {
break;
}
}
int xTwo = 0;
for (int x : nums) {
if (((x >>> k) & 1) == 1) {
xTwo ^= x;
}
}
return new int[] {xTwo, xOne ^ xTwo};
}
}
更多的leetcode的经典算法,查看我的leetcode专栏,链接如下:
我的微信二维码如下,欢迎交流讨论
欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧,都是干货!
微信订阅号二维码如下:
最新文章
- logging 模块
- 孙鑫视频学习:“operator +=” 不明确的问题解决方法
- git 解决冲突
- Hadoop实战4:MapR分布式集群的安装配置及shell自动化脚本
- HDU 1052
- J2EE分布式事务中的提交、回滚方法调用异常。
- 从assemblyer Instructure deepth understander C principle
- [已解决问题] Could not find class XXX referenced from method XXX.<;YYY>;
- C#句柄使用
- 109.110.100.56 samba用户名 PAS, 密码 111111
- 深入理解setTimeout和setinterval
- 【Swift】 iOS开发容易产生Bug的地方
- “Nested exception: 前言中不允许有内容";错误处理
- 使用sstream来进行类型转换
- 【九校3D2T3】世界第一的猛汉王
- jmeter作用域规则
- 11.7 NOIP模拟赛
- unity3d如何快速接入渠道SDK之Unity篇
- lr场景运行报错的解决方法
- python-pycharm控制台输出带颜色