题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

思路：
1.用栈的括号匹配思想。
2.遍历数组元素，如果栈为空，直接入栈；
3.如果栈不为空，对比栈顶元素和当前元素，如果当前元素与栈顶元素相同，则入栈；否则弹出栈顶元素。
4.遍历结束后，继续判断：
            1.如果数组长度是偶数：栈不为空，栈顶元素即为超过数组长度一半的数；为空，说明不存在，已相互抵消
            2.如果数组长度为奇数，最后栈中肯定有元素：
                    1.栈中元素不止一个，栈顶元素即为超过数组长度一半的数
                    2.栈中元素只有一个，重新遍历一次数组，计算该元素在原数组中的个数即可。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include<string>
#include <vector>
class Solution
{
public:void findNumber(vector <int> &vec){int *stack = new int[vec.size()];//根据数组长度来申请栈空间int top = -1; //栈顶指针for (int i = 0; i < vec.size(); i++){if (top == -1)//1.栈为空直接入栈，{stack[++top] = vec[i];continue;}if (stack[top] == vec[i])//2.栈不为空，当前元素与栈中元素相同，入栈{stack[++top] = vec[i];}else	//3.当前元素与栈中元素不同，出栈{top--;}}//遍历结束if (vec.size() % 2 == 0)//1.数组长度偶数，如果栈空，不同与不同元素直接已抵消，不存在{if (top == -1){cout << "不存在超过一半的数" << endl;}else	//2.栈不空，栈顶元素就是结果{cout << "数组中超过一半的数为:";cout << stack[top] << endl;//否则栈顶元素就是超过一半的数}}else//1.数组中的元素是奇数，需要考虑栈中只有一个元素的情况{if (top > 0)//栈中元素不止一个，栈顶元素就是结果{cout << "数组中超过一半的数为:";cout << stack[top] << endl;//}else if (top == 0)//栈中元素只有一个{int k=0;//重新遍历数组,k去记录栈顶元素在数组中的个数。for (int i = 0; i < vec.size(); i++){if (vec[i] == stack[top]){k++;}}if (k > vec.size()/2)//超过一半输出结果{cout << stack[top] << "是数组中超过一半的数" << endl;}else{cout << "不存在超过一半的数" << endl;}}else//栈为空，不存在{cout << "不存在超过一半的数" << endl;}}delete[]stack;}
};
void test01()
{	//测试1vector <int> vec1 = { 1, 2, 3, 2, 2, 2, 5, 4, 2 };Solution s1;s1.findNumber(vec1);//测试2vector <int>vec2 = {3,3,3,3,3,3,6,69,699,69,69,3};s1.findNumber(vec2);
}
int main()
{test01();system("pause");return EXIT_SUCCESS;
}