136. 只出现一次的数字
一句话套路全体异或,成对的自动抵消
题目描述
给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
示例 1 :
输入:nums = [2,2,1]
输出:1
示例 2 :
输入:nums = [4,1,2,1,2]
输出:4
示例 3 :
输入:nums = [1]
输出:1
提示:
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- 除了某个元素只出现一次以外,其余每个元素均出现两次。
思路
时间
O(n)空间
O(1)思路
全部异或。出现两次的互相抵消成 0,剩下的就是那个落单的。
不需要额外空间,O(1) 空间 O(n) 时间,是本题的最优解。
推广
Q137 其余出现 3 次 -> 逐位统计 mod 3;
Q260 有两个落单 -> 全体异或得 x^y,取最低位 1 当分组依据,组内各异或一次。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0136 {
class Solution {
public:
int singleNumber(vector<int>& nums) {
int x = 0;
for (int v : nums) x ^= v;
return x;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0136::Solution s;
vector<int> a{2, 2, 1};
CHECK_EQ(s.singleNumber(a), 1);
vector<int> b{4, 1, 2, 1, 2};
CHECK_EQ(s.singleNumber(b), 4);
vector<int> c{1};
CHECK_EQ(s.singleNumber(c), 1);
vector<int> d{-1, -1, -2}; // 负数:异或按位运算,符号无所谓
CHECK_EQ(s.singleNumber(d), -2);
vector<int> e{0, 0, 7};
CHECK_EQ(s.singleNumber(e), 7);