每日OJ题_位运算②_力扣136. 只出现一次的数字+力扣260. 只出现一次的数字 III

目录

①力扣136. 只出现一次的数字

解析代码

力扣260. 只出现一次的数字 III

解析代码

①力扣136. 只出现一次的数字

136. 只出现一次的数字

难度 简单

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

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

示例 1 ：

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

示例 2 ：

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

示例 3 ：

输入：nums = [1]
输出：1

提示：

• 1 <= nums.length <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

解析代码

之前写过了，以前讲异或讲过的单身狗：

异或(^)运算的运算律（解决只出现一次的数字（单身狗）问题）
a ^ 0 = a
a ^ a = 0
a ^ b ^ c = a ^ ( b ^ c)

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

力扣260. 只出现一次的数字 III

260. 只出现一次的数字 III

难度 中等

给你一个整数数组 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 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• 除两个只出现一次的整数外，nums 中的其他数字都出现两次

解析代码

这也可以用排序，但这是以前写过的找两个单身狗的题：时间复杂度为O（N）

        如果我们按照只出现一次的数字的思路直接异或 肯定只会出来一个四不像数，假设数组1 2 3 3 1 4，我们把 两个单身狗分成两个组。而组中其他的数字就都不是单身狗。

        此时我们在分组异或就分别得到了2个单身狗，问题是以什么为依据分组？依据 二进制位 异或把相同的数字变成0，不同的数字变成1，根据1在哪位 就说明单身狗这个的二进制位不同 ，按照这个二进制位分（这就是那个四不像的数）两个单身狗是不可能进到一组的。

        ① 我们依然把数组中所有数字异或到一起 然后判断这个数字的二进制位 比如有两个单身狗2和40010 和0100最后异或完毕得到的二进制位是 0110 说明两个单身狗数字的二进制最后位是相等我们左移一(cnt)位得到了1 就说明 两个单身狗数字的倒数第二位二进制数 不相等

        ② 让数组中所有的数字左移一(cnt)位 如果等于 1 放进第一个数组中。如果等于0 放进第二个数组中。

        ③ 把数组中的数字全部异或就得到了 2个单身狗

class Solution {
public:
	vector<int> singleNumber(vector<int>& nums) {
		int sum = 0;
		for (const auto& e : nums)
		{
			sum ^= e;
		}
		int cnt = 0;
		for (int i = 0;i < 32;++i)
		{
			if (sum & (1 << i))// 第几位是1结果就是1
			{
				cnt = i;// 记录下来
			}
		}
		vector<int> v = { 0,0 };// C++11的初始化,类似数组
		for (const auto& e : nums)
		{
			if (e & (1 << cnt))
			{
				v[0] ^= e;
			}
			else
			{
				v[1] ^= e;
			}
		}
		return v;
	}
};