给定一个整数数组，其中有一个数字的出现次数大于总数组大小的一半。

思路一：快排，时间开销O(nlogn)，空间开销O(logn)，然后去数组的中间那个数字即可

思路二：采用打擂台的方法。只需要O(n)的时间开销，O(1)的空间开销。维护一个champion记录守擂人，count记录守擂人的生命数。然后依次遍历整个数组，如果数字相同则生命数+1，如果数字不同，则生命-1，如果生命降到0，则换上新的擂主。由于目标数字出现的个数占总的一半以上，因此目标数字作为守擂人一定能够站到最后。

1. class Solution {
2. public:
3. int majorityElement(vector<int> &num) {
4. int champion = num[0];
5. int count = 1;
6. for (size_t i = 1; i < num.size(); i++)
7. {
8. if (count == 0)
9. {
10. champion = num[i];
11. count = 1;
12. continue;
13. }
14. if (champion == num[i])
15. {
16. count++;
17. }
18. else
19. count--;
20. }
21. return champion;
22. }
23. };