【举一反三】只出现一次的数字-Toy模板网

这篇具有很好参考价值的文章主要介绍了【举一反三】只出现一次的数字。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本文，讲位运算——异或运算。因为题干中说明要线性时间复杂度，所以采用位运算进行操作，而没有采用哈希表。

1.只出现一次的数字 I

2.只出现一次的数字 II

3.只出现一次的数字 III

1.只出现一次的数字 I

136. 只出现一次的数字 - 力扣（LeetCode）

题目：

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

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

示例 1 ：

输入：nums = [2,2,1]

输出：1

从一个成对数组中找到落单的元素。很显然我们可以使用异或运算。（相同为0，不同为1）

两个相同数字做异或运算，结果为0。可以帮我们排除掉成对的数字。

0和任何数字进行异或运算，都得到这个数字本身。

代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int value=0;
        for(auto e:nums)
        {
            value^=e;
        }
        return value;
    }
};

2.只出现一次的数字 II

137. 只出现一次的数字 II - 力扣（LeetCode）

题目：

给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素。

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

示例 1：

输入：nums = [2,2,3,2]

输出：3

本题，如果我们继续简单的使用异或，我们会发现最后结果是2^3，没办法得到正确答案。我们可以换个思路题中强调每个元素恰好出现三次，我们从次数的角度出发，考虑该位值为1的次数取模。

数的每一位只有0或1。首先我们考虑第一位，再依次类推直到第32位结束，答案元素的每一位为0或者为1我们都是已知，即得到该答案元素。

如果非答案元素第一位为0，则有：

答案元素第一位为0，总共0个1，0%3=0

答案元素第一位为1，总共1个1，1%3=1

如果非答案元素第一位为1，则有：

答案元素第一位为0，总共3个1，3%3=0

答案元素第一位为1，总共4个1，4%3=1

例子：

【举一反三】只出现一次的数字

代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res=0;
        for(int i=0;i<32;i++)
        {
            int sum=0;    //统计值为1的次数
            for(auto& e:nums)
            {
                sum+=((e>>i)&1);
            }
            if((sum%3)==1)
            {
                res|=(1<<i);    //与0移位或运算
            }
        }
        return res;
    }
};

时间复杂度：O(n logC)，其中n是数组长度，C是数据范围，本题int数据类型，logC=32。

空间复杂度：O(1)

3.只出现一次的数字 III

260. 只出现一次的数字 III - 力扣（LeetCode）

题目：

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

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

示例 1：

输入：nums = [1,2,1,3,2,5]

输出：[3,5]

解释：[5, 3] 也是有效的答案。

本题，还是在异或运算的基础上进行拓展，我们观察题目可以发现，这道题目对所有元素异或后的结果也是2个不同的元素进行异或，而其他元素频数都是2如题目I一样消除了。

也就是说我们可以直接从异或的结果得到启发，某位值为1，就表明两个答案在该位的值不同。我们可以从这个角度为出发点进行切入，对数组分组！两个答案一定在不同的组中。

思路：

已知x^x==0。定义数组的异或和为该数组所有元素的异或。

求出nums的异或和xor，可知xor为两个目标元素的异或。

找到xor中为1的二进制位，假设是第k位。这说明两个目标元素在第k位上不相同。

根据第k位是0还是1，把nums分为两组，这样两个目标元素一定位于不同的组。

分别求出两组的异或和，即得到两个目标元素。

例子：

【举一反三】只出现一次的数字 代码：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int>ans(2);
        int value=0;
        for(auto& e:nums)
        {
            value^=e;
        }
        int k=0;
        while((value&1)==0)
        {
            value>>=1;
            ++k;
        }
        int ans1=0,ans2=0;
        for(auto&e:nums)
        {
            if(((e>>k)&1)==0)
            {
                ans1^=e;
            }
            else
            {
                ans2^=e;
            }
        }
        ans[0]=ans1;
        ans[1]=ans2;
        return ans;
    }
};

【举一反三】只出现一次的数字