只出现一次的数字
# 📃 题目描述
题目链接:
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
# 🔔 解题思路
算是面试高频题了
主要利用二进制中异或的特征
0 ^ 1 = 1
0 ^ 0 = 0
也就是,二进制中,0 和任意数的异或结果都是任意数本身
所以,两个相同的二进制数进行异或,就是 0
已知数组中除了某个元素只出现一次以外,其余每个元素均出现两次
依次执行异或操作,最终的出来的结果就是那个只出现一次的元素
class Solution {
public int singleNumber(int[] nums) {
int res = nums[0];
for (int i = 1; i < nums.length; i ++) {
res ^= nums[i];
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:O(1)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10