LeetCode137只出现一次的数字——位运算
2024-09-08 16:52:16
题目
题目描述:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现三次。找出那个只出现一次的元素。
说明:你的算法应该具有线性时间的复杂度。你可以不使用额外的空间来实现吗?
思路
题目要求线性复杂度,一般的算法做不到,不难想到用位运算。但怎么进行位运算,比较难想到。
b = (b ^ x) & ~a;
a = (a ^ x) & ~b;
^ 相当于除去原有元素,添加新元素, a &~ b 相当于从a集合中除去b集合中的所有元素。
int len = nums.size();
for(int i =;i < len;++i)
{
b = (b ^ nums[i]) & ~a;
a = (a ^ nums[i]) & ~b;
}
出现一次的存在b中,第二次出现从b中清除同时会存在a中,第三次出现会从b中清除。最终出现一次的都存在b中,出现两次的都存在a中。
例如:[1,2,2,1,1,2,99]
b={0} | {1} | {1,2} | {1} | {0} | {0} | {0} | {99} |
a={0} | {0} | {0} | {2} |
{1,2} |
{2 | {0} | {0} |
代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
int a = , b = ;
for (auto x : nums) {
a = (a ^ x) & ~b;
b = (b ^ x) & ~a;
}
return a;
}
}; static const auto __lamda = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
续:
朋友面试竟然遇到了,前面的算法很讲究技巧性,不通用,补充一个较通用的方法:
int数组,32位,用一个32位的int数组,每一位记录值在该位出现1的次数。
其余元素出现3次,最后加起来肯定 %3 = 0。剩下的就是只出现一次的。
int bits[]; int singleNumber(vector<int>& nums)
{
int res = ;
for(int i = ;i <;i++)
{
for(int j = ;j < nums.size();j++)
{
bits[i] += (nums[j]&);
nums[j] >>= ;
}
} for(int i = ;i < ;i++)
if(bits[i] % ) res += ( << i); return res;
}
参考链接:
1. https://leetcode-cn.com/problems/single-number-ii/comments/
2. https://www.cnblogs.com/fanguangdexiaoyuer/p/11585950.html
最新文章
- [原创]-bash: iostat: command not found解决办法
- Yii 框架里数据库操作详解-[增加、查询、更新、删除的方法 &#39;AR模式&#39;]
- Python的平凡之路(11)
- 如何理解和使用Java package包
- 七大查找算法(附C语言代码实现)
- 为 PHP 开发者准备的 12 个调试工具
- VPS技术介绍以及分析
- JavaScript forEach方法
- Unity3D Object.DontDestroyOnLoad 备忘
- 十年linux命令总结
- Foxmail 7.0破解版,拷贝到新机器后,发送邮件乱码问题
- Java语言的特性
- 【一天一道LeetCode】#130. Surrounded Regions
- radhat6.6上安装oracle12c RAC (二)
- mysql的数据类型和字段属性
- 数据结构【查找】—平衡二叉树AVL
- BZOJ3674 可持久化并查集加强版 可持久化 并查集
- android 6 中init.rc的生成过程【转】
- HTML&CSS精选笔记_CSS高级技巧
- GBDT XGBOOST的区别与联系
热门文章
- O(n&#178;)、O(n)、O(1)、O(nlogn)
- HTTP协议 (一) HTTP协议详解
- bootstrap3.0学习笔记记录1
- Apache POI组件操作Excel,制作报表(四)
- 二:多线程--GCD
- bzoj1090 [SCOI2003]字符串折叠——区间DP
- Extjs 4 MVC中全局配置文件
- vi常用设置
- HDU-ACM“菜鸟先飞”冬训系列赛——第9场
- NOIp2013 货车运输 By cellur925