`
bcyy
  • 浏览: 1810088 次
文章分类
社区版块
存档分类
最新评论

LeetCode Single Number I & II 都符合两个问题额外要求的 通用解法 与 思考过程

 
阅读更多

Single Number

Given an array of integers, every element appearstwiceexcept for one. Find that single one.

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

Single Number II

Given an array of integers, every element appearsthreetimes except for one. Find that single one.

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

首先本能地想到一个算法,可是脑子一转,觉得是要O(n*n)时间复杂度。编译一下,果然没通过。程序如下:不过我觉得本算法最简单,而且通用性是最好的。

int singleNumber(int A[], int n) {
		for(int i = 0; i < n; i++)
		{
			if(count(A, A + n, A[i])<2)
				return i;
		}
	}

然后搜肠刮肚想想那个算法可以优化为时间O(n)的复杂度的?分治?减治?贪心?动态规划???想多了。

好吧,本能地分析吧:

1.要求复杂度为O(n),白话点说也就是不能在一个n次循环里面添加任何循环,前面之所以失败就是因为这个原因。但是可以在循环外添加循环!!!

2. 既然可以在查找循环外添加循环,那么添加什么循环好呢?排序吧,没错!排序的数列干什么都方便!(感觉这个结论也适用很多地方)

排序之后就可以很方便地计算一个数在数列中出现了多少次了。一连出现多少次就是总共出现多少次了,方便吧。O(∩_∩)O~

然后开始写代码了,wait!我觉得动手之前还是先考虑一下特殊情况吧。特殊情况一般是边界问题:

1. 如果数列外空呢?

2如果第一个是single number呢?

3如果最后一个是single number呢?

好了,分析完就可以写代码了!下面代码适合两个问题,只需要把出现次数修改为对应的2或3次数就可以了。而且不需要额外的空间!

//通用性好,适合两种情况
	int singleNumber(int A[], int n) {
		//特殊情况1,2
		if(n<=0) return -1;
		if(n==1) return A[0];

		sort(A, A + n);
		int j = 1;
		for(int i = 0; i < n - 1; i++)
		{
			if(A[i] == A[i+1])
				j++;
			else 
			{
				if(j<2) return A[i];//这里修改为j<3那么就可以适用于single number II了。
 				j = 1;
			}
		}

		//特殊情况3 最后一个是single number的特殊情况
		return A[n-1];
	}


相对简单。


2014-3-6更新:


好了,更新不说通用性了。上面的基本排序处理的确是很通用的,属于基本算法内容了,没什么值得深入探讨的。

想不到这篇文章有幸可以有这么多人阅读。
这里更新下解说。
本题类型有三种解法的:
1 如上面的排序后处理的方法
2 利用map处理,效率也接近O(n)
3 位运算操作解法-这里也主要可以分两种解法

下面程序是利用unordered_map解Single number I的程序(Single number II是一样道理):

//2014-2-18 update
	int singleNumber(int A[], int n) 
	{
		unordered_map<int, bool> ump_ii;
		for (int i = 0; i < n; i++)
		{
			if (!ump_ii.count(A[i])) ump_ii[A[i]] = true;
			else ump_ii.erase(A[i]);
		}
		return ump_ii.begin()->first;
	}


下面是Single number I 的位运算解法,思路就是每位bit出现2次就清零,所以可以不断异或运算得出最终结果:

//2014-2-18_2 update
	int singleNumber(int A[], int n) 
	{
		int ans = 0;
		for (int i = 0; i < n; i++) ans ^= A[i];
		return ans;
	}



Single number II 的位运算两种解法-- 参考leetcode论坛的代码:

方法一,int的32个bit逐个处理-这个方法还算简单的了:

int singleNumberII_36(int A[], int n)
{
	int ans = 0;
	for (int i = 0; i < 32; i++) 
	{
		int c = 0, d = 1<<i;
		for (int j = 0; j < n; j++)
			if (A[j] & d) c++;

		if (c%3) ans |= d;
	}
	return ans;
}


方法二,进位,掩码清零法-本方法还是挺难理解的,要很小心,否则,很容易出错的,对位运算不熟悉是很难写出来的。

int singleNumber(int A[], int n)
{
	int one = 0, two = 0;
	for (int i = 0; i < n; i++)
	{
		two |= A[i] & one;//two 积累值
		one ^= A[i];//one不断求反
		int t = one & two;//第三次的时候one和two都保留了该位的值
		one &= ~t;//清零出现三次的该位的值
		two &= ~t;
	}
	return one;
}

好了,网上也有其他Single number II的变异的位运算算法,不过都不太好理解。Single NumberII可以说高达5星级难度了。

不过上面的位运算方法一还是算好理解的了,而且也比较容易就可以用在其他情况,比如所有numbers都出现5次其中一个除外,面试的时候我觉得应该是首推算法吧。


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics