数组中出现次数超过一半的数字
数组中有一个数字出现次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
由于数字2在数组中出现了5次，超过数组长度一半，因此输出2
分析：
为了后面的解释，我们首先定义：
对于数组A，出现次数超过一半的数记为H(A)
还是以之前的数组A{1,2,3,2,2,2,5,4,2}为例,首先有H(A) = 2，我们观察一下这个2的特点：
如果把前两个数1和2去掉，剩下的数组A'是{3,2,2,2,5,4,2}，H(A')依然为2！
更进一步，我们可以这么想，既然前两个数去掉之后不影响找出现次数超过数组长度的一半的数字，那么任意去掉相邻的两个数字也不影响呢。
也就是说对于任意数组A和A去掉两个相邻数字的子数组A'是否都有:H(A) = H(A')
很不幸，这个结论也不成立，因为如果在刚刚的数组A中去掉连续的两个2，就不对了。但是只要稍稍把结论修改一下就是成立的：
对于任意数组A，去掉A中任意两个相邻但不相等的数，得到数组A',总有H(A) = H(A')
结论很好证明：设H(A) = p,去掉的两个数中最多有一个p，由于p原来出现的次数大于n/2，现在p-1自然一定大于(n-2)/2。所以H（A'）= p。
实现：
有了刚刚的结论，再看这个数组就简单多了。只要把数组从头到尾遍历一遍，剔除相邻的不同的数就可以。比如数组中有一段是{1，2，3，4}，可以预见到，有可能是{2，3}先被比较，然后被剔除，接着是{1，4}变成相邻的，接着被剔除。
为了避免反复循环，在一个循环里解决问题，自然而然的想到了一个数据结构——“栈”。
只要对于数组中的每一个元素，如果栈为空或这个元素与栈顶元素相同，则这个元素入栈，否则栈顶元素出栈即可。这样一来，不相同的数即使不相邻，迟早也会一起出栈（可以把用来和栈顶做比较元素想象为先入栈再出栈）。
所以这样一来，代码会非常简洁优雅：
int findNumber(std::vector<int> v){
std::stack<int> stack = std::stack<int>();
for (int i = 0; i < v.size(); ++i) {
if (stack.empty() || stack.top() == v[i]) {
stack.push(v[i]);
}
else{
stack.pop();
}
}
return stack.top();
}