LeetCode 练习——260. 只出现一次的数字 III
2022/1/24 6:06:11
本文主要是介绍LeetCode 练习——260. 只出现一次的数字 III,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 1.题目描述
- 2.思路
- 2.1 代码
- 2.2 测试结果
- 3.总结
1.题目描述
只出现一次的数字 III
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶:你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?
示例 1:
输入:nums = [1,2,1,3,2,5] 输出:[3,5] 解释:[5, 3] 也是有效的答案。
示例 2:
输入:nums = [-1,0] 输出:[-1,0]
示例 3:
输入:nums = [0,1] 输出:[1,0]
2.思路
2.1 代码
由于所有数字中只有两个数(a和b)出现奇数次,其余数出现偶数次,那么将所有的数进行异或,则可以得到这两个出现奇数次的数异或结果 a ^ b。
假如 a ^ b 的结果为01101000,那么他与自己的相反(10011000)进行求或则可以得到该数右侧第一个1出现的位置(00001000),如下所示。当知道 a ^ b的右侧第一个数为1时,则a和b的该位置一定不同(异或不同为1相同为0)。那么再次遍历数组,并且数组中的数该位置为1的数进行异或运算,便可以得到a、b中的某一个数。
最后再用 a ^ b 的结果与得到的其中一个数进行异或运算,便可以得到另外一个数。
class Solution { public int[] singleNumber(int[] nums) { int eor = 0; for (int i = 0; i < nums.length; i++) { eor ^= nums[i]; } int rightFirstOne = eor & (-eor); int eorCheck = 0; for (int i = 0; i < nums.length; i++) { if ((nums[i] & rightFirstOne) != 0){ eorCheck ^= nums[i]; } } return new int[]{eorCheck, eor^eorCheck}; } }
2.2 测试结果
通过测试
3.总结
- 数组中的所有数字依次异或可以得到出现奇数次的两个数异或结果
- 一个数异或自己的相反数,便可以得到该数右边第一次1出现的位置
- 通过第一次出现1的结果将原数组分成两拨,一拨该位置为1,另一拨该位置为0
- 通过该位置为1的数进行异或,便得到a、b中的一个数
- 最后通过 a ^ b ^ a = b 或者 a ^ b ^ b = a 得到另外一个数
这篇关于LeetCode 练习——260. 只出现一次的数字 III的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding