HHot 100C++ 图解

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 当分组依据,组内各异或一次。

图解

4 0 1 1 2 2 1 3 2 4
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/17_tricks.cpp10 行
namespace lc0136 {
class Solution {
 public:
  int singleNumber(vector<int>& nums) {
    int x = 0;
    for (int v : nums) x ^= v;
    return x;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q136_single_number11 行
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);

↑↓ 选择↵ 打开/ 随时唤起