【更新】【leetcode刷题】T35-只出现一次的数字 III

木又AI帮

修改于 2019-07-18 10:00:15

2430

修改于 2019-07-18 10:00:15

【英文题目】（学习英语的同时，更能理解题意哟~）

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.

Example:

Input:  [,,,,,]
Output: [,]

Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

【中文题目】

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

示例 :

输入: [,,,,,]
输出: [,]

注意：

结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

【思路】

本题和【T33-只出现一次的数字】【T34-只出现一次的数字 II】类似，有两种解法：一是使用hash表，二是利用到数学。

hash表即为：使用字典存储元素及其个数，对所有元素进行计数，当元素个数为3时，弹出字典

数学方法即是：对所有元素求异或，由于有两个元素只出现一次，那么异或结果肯定不为0。根据异或结果二进制的最后一位为1的位（比如第i位），将所有元素分为两类，一是第i位为1的数，二是第i位为0的数。那么原问题转换为两个【T33-只出现一次的数字】这样的问题，分别对两类元素进行异或即可得到结果。

【代码】

python版本

hash

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        d = {}
        for n in nums:
            d[n] = d.get(n, ) + 
            if d[n] == :
                d.pop(n)
        return d.keys()

二进制

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = 
        for n in nums:
            res ^= n
        # 最后一位为1的位
        bit = res & (-res)
        result = [, ]
        for n in nums:
            if n & bit == :
                result[] ^= n
            else:
                result[] ^= n
        return result

C++版本

hash

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        map<int, int> d;
        for(auto n: nums){
            d[n]++;
        }
        vector<int> res;
        for(auto di: d){
            if(di.second == )
                res.push_back(di.first);
        }
        return res;
    }
};

二进制

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int res=;
        for(auto n:nums){
            res ^= n;
        }
        res &= (-res);
        vector<int> result(, );
        for(auto n:nums){
            if((n & res) == )
                result[] ^= n;
            else
                result[] ^= n;
        }
        return result;
    }
};

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-04-12，如有侵权请联系 cloudcommunity@tencent.com 删除

c++