LeetCode Single Number I & II 都符合两个问题额外要求的 通用解法 与 思考过程
Single Number
Given an array of integers, every element appears twice except 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 appears three times 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）时间复杂度。编译一下，果然没通过。程序如下：不过我觉得本算法最简单，而且通用性是最好的。
[cpp]
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次数就可以了。而且不需要额外的空间！
[cpp]
//通用性好，适合两种情况
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，不过特殊要求下可以用吧，当开开眼界，贴出如下：
[cpp]
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;
}
看到倒数第二句了吧，这个是关键，做异或运算，所以说技巧性很强，而且很底层。效率很高，比第二种解法效率要高。但是不通用.
补充：软件开发 , C++ ,
