只出现一次的数字

题目链接

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
注意：要求是线性时间复杂度同时不使用额外的空间

样例输入

[2,2,1]

样例输出

解题思路

总所周知，两个一样的数进行异或操作的结果就是零。所以我们可以通过异或操作将成对的数字消掉，最后的结果便是只出现一次的数字了。

AC代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        int len = nums.size();
		for (int i = 0; i < len; i++){
			ans ^= nums[i];
		}
		return ans;
    }
};

只出现一次的数字 II

题目链接

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
注意：要求是线性时间复杂度同时不使用额外的空间

样例输入

[2,2,3,2]

样例输出

解题思路

参考自
根据上一题的经验，两个一样的数字可以通过异或来消除。那三个数时要怎么消除呢？我们不妨定义两个变量a和b，假设数组中数字X出现了三次
X第一次出现时

1	a = a ^ X;

X第二次出现时

1	b = b ^ X;

X第三次出现时

1 2	a = a ^ X; b = b ^ X;

到这一步还是非常通俗易懂的。但是如何判断X是第几次出现呢？在别人的博客看到如下的公式

1 2	a = (a ^ X) & ~b; b = (b ^ X) & ~a;

在这里除了膜拜能想到这个公式的神仙，我什么也做不了。这也太nb了。

AC代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
		int len = nums.size();
		int a = 0;
		int b = 0;
		for (int i = 0; i < len; i++){
			a = (a ^ nums[i]) & ~b;
			b = (b ^ nums[i]) & ~a;
		}
		return a;
    }
};

只出现一次的数字 III

题目链接

题目描述

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

样例输入

[1,2,1,3,2,5]

样例输出

[3,5]

解题思路

与第一题一样，先将所有数字异或操作一遍，然后会得到只出现一次的那两个数字异或的结果。我们都知道异或的意义在于不同则为1，那我们可以通过这个不同位将数组重新划分为两部分，一部分为该位置为0，另外一部分为该位置为1。如何快速找到二进制表达式中最低位的1所对应的值可以通过lowbit()函数来获取

1
2
3

int lowbit(int x){
	return x & -x;
}

AC代码

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
		int len = nums.size();
		int temp = 0;
		for(int i = 0; i < len; i++){
			temp ^= nums[i];
		}
		temp = temp & (-temp);
		int ans1, ans2;
		ans1 = ans2 = 0;
		for(int i = 0; i < len; i++){
			if (nums[i] & temp)
				ans1 ^= nums[i];
			else
				ans2 ^= nums[i];
		}
		vector<int> ans;
		ans.push_back(ans1);
		ans.push_back(ans2);
		return ans;
    }
};