LeetCode 136. 只出现一次的数字
难度: e a s y \color{Green}{easy} easy
题目描述
给你一个 非空 整数数组 n u m s nums nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
示例 1 :
输入:nums = [2,2,1]
输出:1
示例 2 :
输入:nums = [4,1,2,1,2]
输出:4
示例 3 :
输入:nums = [1]
输出:1
提示:
- 1 < = n u m s . l e n g t h < = 3 ∗ 1 0 4 1 <= nums.length <= 3 * 10^{4} 1<=nums.length<=3∗104
- − 3 ∗ 1 0 4 < = n u m s [ i ] < = 3 ∗ 1 0 4 -3 * 10^{4} <= nums[i] <= 3 * 10^{4} −3∗104<=nums[i]<=3∗104
- 除了某个元素只出现一次以外,其余每个元素均出现两次。
算法
(位运算)
- 两个相同的数字经过异或之后会变为 0。
- 将数组所有元素异或在一起即可得到出现 1 次的元素值。
复杂度分析
-
时间复杂度:仅遍历一次数组,故时间复杂度为 O ( n ) O(n) O(n)
-
空间复杂度 : O ( 1 ) O(1) O(1),仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (auto num : nums) res ^= num;
return res;
}
};
相关文章
- Java实现 LeetCode 788 旋转数字(暴力)
- Java实现 LeetCode 738 单调递增的数字(暴力)
- Java实现 LeetCode 719 找出第 k 小的距离对(二分搜索法+二分猜数字)
- Java实现 LeetCode 477 汉明距离总和
- Java实现 LeetCode 476 数字的补数
- Java实现 LeetCode 448 找到所有数组中消失的数字
- Java实现 LeetCode 402 移掉K位数字
- Java实现 LeetCode 299 猜数字游戏
- Java实现 LeetCode 287 寻找重复数
- Java实现 LeetCode 241 为运算表达式设计优先级
- Java实现 LeetCode 241 为运算表达式设计优先级
- Java实现 LeetCode 137 只出现一次的数字 II(二)
- Java实现 LeetCode 137 只出现一次的数字
- [LeetCode] Ugly Number II
- 【LeetCode Python实现】260. 只出现一次的数字 III(中等)
- Leetcode 299. 猜数字游戏
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- LeetCode 237. 删除链表中的节点