leetcode 11.09-11.15

2020-11-15

137 只出现一次的数字II
260 只出现一次的数字III

137. 只出现一次的数字II

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

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]
输出: 3
示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：统计二进制每一位1的数目，对3取余，组合起来为答案

AC代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (auto num : nums) {
                sum += (num >> i) & 1;
            }
            res ^= ((sum % 3) << i);
        }
        return res;
    }
};

官方题解的状态机转换没看懂，太难理解了= =

260. 只出现一次的数字III

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

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]
注意：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：先异或一遍整个数组，因为存在两个不同的数字，最后得到的数字$tmp$不为0；找到$tmp$二进制中为1的位置$index$，表明最后的两位结果数字，一个在$index$是0，一个在$index$是1，利用这个特性将整个数组分成$index$位为1和$index$为0的两组数组；分别在这两个数组里找唯一不同的数字即可。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        tmp = 0
        for num in nums:
            tmp ^= num
        for i in range(32):
            if (tmp >> i) & 1 == 1:
                index = i
                break;
        ret = [0, 0]
        for num in nums:
            if (num >> index) & 1 == 0:
                ret[0] ^= num
            else:
                ret[1] ^= num
        return ret