面试题-仅出现一次的元素

仅出现一次的元素

• 涉及知识点：散列表、位运算

题目

（英文）
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.

（中文）
给定一个整数数组，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出仅出现一次的那两个元素。要求时间复杂度在O(N)内。

示例输入:

[1, 2, 1, 3, 2, 5]  

示例输出：

[3, 5]  

思路描述

思路1：排序+遍历

对序列排序，后遍历所有元素，通过相邻元素是否有相同值来判断是否满足条件，输出。

常规排序方案的时空复杂度如下：

• 时间复杂度 O(N*log(N))
• 空间复杂度 O(1)

此时解法不满足要求，可给到2分，若能给出计数排序（时间复杂度O(N)）法，可给到3分。

思路2：散列表+遍历

遍历每个元素，使用散列表存储元素值到数量的映射关系，再遍历散列表找出其中value为1的key，输出。

该方案的时空复杂度分析如下：

• 时间复杂度 O(N)
• 空间复杂度 O(N)

此时为次优解，可延伸提问对散列表的理解（如遍历结果是否有序，两个元素输出顺序是否确定），回答正确可给到4分

思路3：位运算

遍历元素，使用异或运算可消除相同的元素，得到所求两个元素的异或结果，从中找出二进制为1的最低位数字，再遍历一次，求出其中一个元素，再与前面结果异或得到另一个元素，输出。

该方案的时空复杂度分析如下：

• 时间复杂度 O(N)
• 空间复杂度 O(1)

此为最优解，可给到5分

解法示例

排序+遍历

hash+遍历

位运算