LeetCode Single Number II

LeetCode Single Number II

Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?


数组中有出现3次的数,但是也有一个出现1次的数,现在要把这个只出现1次的数找出来。要求是线性时间复杂度和常数空间复杂度。

相比于LeetCode Single Number有难度。网上看到一个很不错的题解,分析得很详细。

初级解法是,把数组中每个数字的对应二进制位加起来,因为3个相同的数对应二进制位加起来之后模3一定等于0,比如5的二进制为101,三个101加起来就是303,每一位模3就是000。所以如果混入了一个只出现一次的数,这样取模之后,剩余位为1的就是我们要找的数的二进制形式。

这种解法需要一个32位的数组,用来统计所有数每一位出现1的次数之和,所以空间复杂度是O(32)=O(1)。时间复杂度的话,相当于O(32n)=O(n),是线性的。完整代码如下:

class Solution {
public:
	int singleNumber(vector<int>& nums) {
		int bit_len = sizeof(int) * 8;
		vector<int> bit(bit_len, 0);
		for (int i = 0; i < bit_len; ++i) {
			for (int j = 0; j < nums.size(); ++j) {
				bit[i] += (nums[j] & 1);
				nums[j] >>= 1;
			}
		}
		int ans = 0;
		for (int i = 0; i < bit_len; ++i) {
			int r = bit[i] % 3;
			ans |= (r << i);
		}
		return ans;
	}
};

本代码提交AC,用时12MS。

高级解法是,使用三个int的每一位表示所有数每一位出现1次数之和的情况,one对应位为1表示这一位出现了1次1,two对应位为1表示这一位出现了2次1,three对应位为1表示这一位出现了3次1。但是one,two,three对应位不可能都同时为1。

通过分析对应位的关系(请看原博客),发现one,two,three可以快速通过位运算计算得到。完整代码如下:

class Solution {
public:
	int singleNumber(vector<int>& nums) {
		int one = 0, two = 0, three = 0;
		for (int i = 0; i < nums.size(); ++i) {
			two |= (one&nums[i]);
			one ^= nums[i];
			three = one&two;
			one -= three;
			two -= three;
		}
		return one;
	}
};

本代码提交AC,用时15MS。

初级解法还是好理解一些,会不会是一个通用的解法呢,比如数组中出现1次和出现4次(甚至k次)的数混在一起,都可以通过模k求解呢?

Leave a Reply

Your email address will not be published. Required fields are marked *