LeetCode 260. 只出现一次的数字 III 中等

1. 260. 只出现一次的数字 III 中等

1. 题目详情

1. 原题链接

LeetCode 260. 只出现一次的数字 III 中等

2. 题目要求

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：
输入：nums = [-1,0]
输出：[-1,0]

示例 3：
输入：nums = [0,1]
输出：[1,0]

提示：
$2<=nums.length<=3\ast 104$
$-231<=nums[i]<=231-1$
除两个只出现一次的整数外，$nums$ 中的其他数字都出现两次

3. 基础框架

● Cpp代码框架

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
    }
};
1
2
3
4
5

2. 解题思路

通过异或把数组$nums$分成分别只包含一个只出现一次的数的两个部分，分别对这两个部分异或从而分别得到这两个部分的结果$ret1$和$ret2$。

1. 思路分析

$(1)$ 如何把这两个只出现一次的不同的数分隔到不同的两部分呢？
突破点就在于，不同的这两个数是不同的$ret1$和$ret2$，两个整数的不同表现在bit位至少有1位是不同的，而数组中其他数都是出现两次，通过这个不同的bit位既可以把$ret1$和$ret2$分开，也会把$nums$中其他的数分开且相同的数一定分在同一组，因为相同的数，bit位一定相同。
$(2)$ 首先对$nums$中所有的数进行异或，等价于$ret1$与$ret2$异或，结果保存在$optRet$中；
$(3)$ 找到$optRet$中一个为1的bit位，把该位置对应的下标记录在$indexBit$中；
$(4)$ 遍历$nums$数组，根据每一个数的$indexBit$位置是0还是1进行分组；
$(5)$ 对于分隔的两组来说，分别对每一组中所有元素进行异或，得到的结果就是这一组中唯一出现的数，记录在$ret1$、$ret2$中；
$(6)$ 返回结果
如何得到具体的某一位bit位？
比如$number=10$，二进制$00000000000000000000000000010010$;
得到第5个bit位，期望第5个bit位是1；
(number >> 4) & 1 ：使number右移4个bit位，再与1按位与的结果就是第5个bit位的值；
number右移4个bit位：$00000000000000000000000000000001$；
再和1按位与：$00000000000000000000000000000001$；

2. 时间复杂度

$O(N)$

第一次遍历$nums$数组计算所有数异或的结果；
第二次遍历至多32次找到第一个不相等的bit位下标；
第三次遍历$nums$数组把数组分成两部分，同时不同组的数之间进行异或，最终得到两个结果；
这三次遍历先后并列进行，$2\ast N+32$次

3. 代码实现

位运算-异或

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int ret1 = 0, ret2 = 0;
        // 得到 单独出现的两个不同的数 异或的结果
        int optRet = 0;
        for(auto& e : nums){
            optRet ^= e;
        }
        // 找到 tmp中第一个为1的bit位，两个不同的数的该bit位的值一个是1，一个是0
        // 通过这个bit位，把nums数组的元素可以分成两个部分：
        // 第一部分，只有一个元素出现一次，其他的元素都出现两次；
        // 第二部分，只有另一个元素出现一次，另外其他元素的元素都出现两次；
        // 这样就使得问题简化为分别在两个数组中找到只出现一次的元素了
        int indexBit = 0;
        while(indexBit < 32){
            if(((optRet >> index) & 1) == 1){
                break;
            }
            indexBit++;
        }
        // 遍历nums数组，第一部分的元素结果在ret1中
        // 第二部分的结果记录在ret2中
        for(auto& e : nums){
            if(((e >> indexBit) & 1) == 1){
                ret1 ^= e;
            }
            else{
                ret2 ^= e;
            }
        }
        return vector<int>{ret1, ret2};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

哈希映射

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> ret;
        ret.reserve(2);
        unordered_map<int, int> m;
        for(auto& e : nums){
            m[e]++;
        }
        for(auto& e : nums){
            if(m[e] == 1){
                ret.push_back(e);
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

$The$ $End$