每日一题-2nd

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

Leetcode 137. 只出现一次的数字 II

题干

给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现 三次。

请你找出并返回那个只出现了一次的元素（记为“答案”）。你必须设计并实现线性时间复杂度的算法且不使用额外空间来找到这个答案。

示例

示例 1：

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

示例 2：

1 2	输入：nums = [0,1,0,1,0,1,99] 输出：99

思路分析

首先看到线性时间复杂度、常数空间复杂度，一定不能使用记录每个数据比对的方法。
又会想到，如果只能遍历常数次，那么相当于把所有数据的信息压缩在常数个数中，所以第一个考虑使用二进制表示。如何把数据出现次数的信息保存在常数个数的数据中？

本人第一印象是有一次矩阵开关灯的题目，用二进制表示第一行开关灯的方法。

现在不妨把每个元素都看成二进制的，以二进制第 $i$ 位为例，那么相同元素，在第 $i$ 的数一定相同。试想，所有除了答案以外的数都出现3次，那么答案在第 $i$ 位上的数必定是所有数据第 $i$ 位上“1”出现次数与3取余（因为如果第 $i$ 位上有3k个1，那么答案在这个位上必然是0；反之，如果有不能被3整除个1，那么答案在这个位上必然是1）。

对于这个第 $i$ 位，我们采用两个二进制数 $a_i,\space b_i$ 来表示 该位上出现1的总次数 mod 3：

$a_ib_i=00\Longrightarrow 第i位上出现了3k个1$ ；
$a_ib_i=01\Longrightarrow 第i位上出现了(3k+1)个1$ ；
$a_ib_i=10\Longrightarrow 第i位上出现了(3k+2)个1$ .

每次输入一个元素，判断：如果第 $i$ 位上是0，则 $a_i,\space b_i$ 不变，否则，按照上面0->1->2->0->…的规律变化。这样，不管元素是以何种顺序输入，只要一个数出现3次，那么这个数对于 $a_i,\space b_i$ 的“影响”就会归0。结束时，没有将 $a_i,\space b_i$ 归0的数对应的就是答案。

下面只需要对 $a_i,\space b_i$ 和输入 $input_i$ 的关系设计时序逻辑电路即可。得到的状态转换式是按位的，C++中只要按位运算即可解决。

本人解答

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (int n : nums) {
            int tmpa = ~n & a | n & b;
            int tmpb = ~a & (b ^ n);
            a = tmpa; b = tmpb;
        }
        return b;
    }
};

题目对比

Leetcode 136. 只出现一次的数字

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

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

评价：相较于137而言，这题非常简单，无需考虑设计逻辑电路，因为按位异或运算的特征：A^0=A，A^A=0，满足两次记录数据的要求。

Leetcode 260. 只出现一次的数字 III

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

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

评价：因为是出现两次和一次，故与136思路相同，都是取异或。最后得到的应该是两个答案的异或值。为了将二者区分，应该先找出两个数在哪一个二进制位上不相同（即异或值为1），并按照这个区分整个数组中所有的数，依此来分别找到两个数（区分所有数时，相同的数一定在一个类里，所以对其他非答案数没有任何影响）。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long ansxor = 0;
        for (int item : nums) ansxor ^= item;
        long exIdx = 1;
        long a = 0, b = 0;
        while ((ansxor & exIdx) == 0) exIdx <<= 1;
        for (int item : nums) {
            if (item & exIdx) a ^= item;
            else b ^= item;
        }
        vector<int> ans;
        ans.push_back(a);
        ans.push_back(b);
        return ans;
    }
};