[LeetCode] 260. Single Number III(位操作)
2024-09-05 02:32:21
Description
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?
思路
题意:给定一个数组,其中除了两个数出现一次外,其他都出现两次,要求在时间复杂度为O(n)空间复杂度为O(1)的条件下找出这两个数。
题解:按照异或的思想,最后可以得到这两个出现一次的数的异或值,那么我们只需对这个异或值lowbit操作,得到其最低位为1的位在哪,然后根据lowbit后得到的值,将数据分为两堆,那么可以知道的是这两个出现一次的数肯定分布在不同的两堆中(因为是对这这两个数的异或值lowbit操作,因此其为1的最低二进制位,这两个数肯定一个数0一个是1),那么问题转化为子问题,有一堆数,出了一个数出现一次外,其他数都出现两次。
class Solution {
public:
//26ms
vector<int> singleNumber(vector<int>& nums) {
int diff = 0,one = 0,two = 0;
vector<int>res;
for (unsigned int i = 0;i < nums.size();i++){
diff ^= nums[i];
}
diff &= (-diff); //lowbit操作
for (unsigned int i = 0;i < nums.size();i++){
if (nums[i] & diff) one ^= nums[i];
else two ^= nums[i];
}
res.push_back(one);
res.push_back(two);
return res;
}
};
最新文章
- Esfog_UnityShader教程_溶解效果Dissolve
- Mac: Jdk版本切换
- Linux内核循环链表经典分析和移植
- 解决Ue4C++使用UMG之类的模块时出现的拼写错误
- svn status 显示 ~xx
- MAC中开发Unity3D
- #import vs. @class
- 用JS写的放大镜
- AndroidPN中的心跳检测
- F - Wormholes
- asp.net [AjaxMethod]
- PHPEXCEL实例-导出EXCEL
- Spring Cloud 学习笔记(二)——Netflix
- 在linux ubuntu下搭建深度学习/机器学习开发环境
- 使用 pandas 导出数据
- Python&#160;一键上传下载&;一键提交文件到SVN入基线工具
- WinRAR从入门到高级的操作技巧集合
- Mybatis 逆向工程学习随笔
- dhroid - eventbus 事件总线
- mac securecrt无法记住密码的解决方法