LeetCode如何查只出现一次的数字
发表于:2024-09-30 作者:千家信息网编辑
千家信息网最后更新 2024年09月30日,这篇文章主要介绍LeetCode如何查只出现一次的数字,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!题目:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两
千家信息网最后更新 2024年09月30日LeetCode如何查只出现一次的数字
这篇文章主要介绍LeetCode如何查只出现一次的数字,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!
题目:
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
思路:
上次做了两数之和的题,对hash印象还深,看到这个题的第一眼就想到hash。
遍历数组,以当前值为key,若当前表中含有该数字,value为2;若不含有,value为1,遍历完后,找表中value值为1的数字,若存在,则返回对应key;否则,不存在这样的数字。
空间复杂度是O(n),不满足不使用额外空间的题目要求,但我想不出什么方法辣,哭了......;
代码:
class Solution { public int singleNumber(int[] nums) { //给定数组非空 Mapmap = new HashMap (); for(int i:nums) { if(map.containsKey(i)) { map.put(i,2); } else map.put(i,1); } for(int j:map.keySet()) { if(map.get(j) == 1) return j; } return -1; } }
demo:
输入:[2,2,1] 输出:1
输入:[4,1,2,1,2] 输出:4
运行结果:
官方解答
解
异或位运算
性质1:如果对0和二进制位做异或运算,得到的仍是这个二进制位。
性质2:如果我们对相同的二进制位做异或运算,返回的结果是0。
性质3:异或运算满足交换律和结合律。
思路
代码
class Solution { public int singleNumber(int[] nums) { int single = 0; for (int num : nums) { single ^= num; } return single; }}
复杂度分析
时间复杂度:O(n)
空间复杂度:O(1)
复习
位运算虽然不是很常见,但是适当的使用可以大量减少开销。
Java中常用的位运算
&:按位与。
|:按位或。
~:按位非。
^:按位异或。
按位与
操作数1 | 0 | 0 | 1 | 1 |
---|---|---|---|---|
操作数2 | 0 | 1 | 0 | 1 |
按位与 | 0 | 0 | 0 | 1 |
按位或
操作数1 | 0 | 0 | 1 | 1 |
---|---|---|---|---|
操作数2 | 0 | 1 | 0 | 1 |
按位或 | 0 | 1 | 1 | 1 |
按位非
操作数 | 0 | 1 |
---|---|---|
按位或 | 1 | 0 |
按位异或
操作数1 | 0 | 0 | 1 | 1 |
---|---|---|---|---|
操作数2 | 0 | 1 | 0 | 1 |
按位异或 | 0 | 1 | 1 | 0 |
以上是"LeetCode如何查只出现一次的数字"这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注行业资讯频道!
操作数
运算
数字
复杂
复杂度
空间
二进制
元素
性质
数组
代码
内容
思路
时间
篇文章
结果
题目
输入
输出
相同
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
悦家互联网科技 怎么样
sql注入修改数据库
网络技术听课体会
关于电子计算机主服务器
静安区技术网络技术均价
php配置服务器
网络安全网络监控预期效果
网络安全手抄报没有字只有画
智能消防软件开发定制
小学生网络安全要求
网络安全主动防御理论
投标软件开发团队人员要求
通联汇成互联网科技有限公司
华为2021软件开发工资
软件开发市场需求及应用
网络安全知识漫画图片
个人如何营造网络安全环境
世界贸易组织数据库考试祝福语
内蒙网络时间与服务器时间的区分
软件开发 进度计划
php用户登录数据库
睿思互联网保险科技大会
网络技术中atm指的是
关于电子计算机主服务器
金山区软件开发创新服务
局域网如何调用sql数据库
济源服务器费用
网络安全周小报内容
北京放心软件开发设施推广
保定软件开发联系方式