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) {
		// IMPORTANT: Please reset any member data you declared, as
		// the same Solution instance will be reused for each test case.
		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];
	}

呵呵，兼顾了效率和通用性，而且相对也简单。

顺便介绍一种问题1的技巧性解法：

它的技巧性太强，对于问题2需要修改很大才能适用：

int singleNumber(int A[], int n) {
		if(n<1)
			return -1;  
		int sNum = 0;  
		for(int i = 0; i < n; i++)  
			sNum ^= A[i];  
		return sNum;  
	}

看到倒数第二句了吧，这个是关键，做异或运算，所以说技巧性很强，而且很底层。效率很高，比第二种解法效率要高。

//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;
	}

//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;
	}