【刷题-LeeetCode】260. Single Number III
2024-10-19 19:03:58
- Single Number III
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.
Example:
Input: [1,2,1,3,2,5]
Output: [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?
解 在只有一个出现一次,其余数字出现两次的数组里面找出现一次的数字通过位异或即可实现。如果能将本题中的两个数字区分开来,问题也就可以解决了。思路同样是异或
- step1:生成mask,将所有的数字都进行异或,最后的结果就是两个出现了一次的数字(记为a, b)的异或结果,这两个数字至少有1位不相等,将异或结果的出现为1的位置作为mask,mask的二进制只有1位是1
- step2:寻找a和b,对于数组中的数字x,如果x&mask是1,说明x可能是a(或b);如果x&mask是0,说明x可能是b(或a)
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int x_or = 0;
for(auto x: nums)x_or ^= x;
int mask = 1;
while((mask & x_or) == 0)mask <<= 1;
int ans1 = 0, ans2 = 0;
for(auto x : nums){
if((mask & x) != 0){
ans1 ^= x;
}else{
ans2 ^= x;
}
}
return {ans1, ans2};
}
};
最新文章
- 如何使用Google Map API开发Android地图应用
- python ImportError: DLL load failed: %1 不是有效的 Win32 应用程序
- Java验证码识别解决方案
- 关于Java项目打包
- Effective Java 70 Document thread safety
- jquery 取的单选按钮组的值
- jQuery基础学习4——jQuery容错性
- getScript 按需加载javascript
- Android系统移植与调试之------->;如何修改Android设备的开机第一阶段Logo
- JavaEE开发之Spring中的条件注解组合注解与元注解
- iOS耗电量测试
- 利用 bat 批量处理命令实现手动控制mysql /Oracle 服务的开启和关闭
- lucene查询索引库、分页、过滤、排序、高亮
- SQL server 存储过程的建立和调用
- Android Studio打包SDK后,为什么没有bundles文件夹?
- ABP实践(2)-ASP.NET Core 2.x版本EntityFrameworkCore(EF)使用mysql数据库
- STM32-跑马灯实验
- LeetCode 929 Unique Email Addresses 解题报告
- 10.25 AITalkUat部署
- HBase常用操作命令
热门文章
- logging模块学习
- 当页面是本地页面时,通过ajax访问tomcat里的action,传递的参数在action里并不能识别
- Linux宝塔面板部署运行jar包
- Redis报错:RDB snapshots, but it is currently not able to persist on disk 处理
- 【九度OJ】题目1445:How Many Tables 解题报告
- 【九度OJ】题目1080:进制转换 解题报告
- 【LeetCode】17. Letter Combinations of a Phone Number 电话号码的字母组合
- 【LeetCode】623. Add One Row to Tree 解题报告(Python)
- 教学日志:javaSE-数组
- 源码分析 SpringCloud 2020.0.4 版本 EurekaClient 的注册过程