题目描述

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

代码:

// 至少三种方法// 1. 遍历统计每个数字次数(O(n^2))// 2. 借助快排思想(O(n))// 3. 设置两个标志位,一个用于记录当前数字,另一个用于计数:向后遍历,当遇到相同的数字时,计数加1;//    当遇到不同的数字时,计数减一;并且当计数为0时,替换为当前数字,计数置为1,继续往后遍历,直到数组最后.(O(n))// class Solution {public:    int MoreThanHalfNum_Solution(vector
    
      numbers) {        if (numbers.size() == 0)            return 0;        int current_num = numbers[0];        int cnt = 1;        for (std::string::size_type index  = 1; index < numbers.size(); index++) {            if (numbers[index] == current_num) {                cnt++;            } else {                cnt--;                if (!cnt) {                    if (index == numbers.size()-1)                        return 0;                    current_num = numbers[index];                    cnt = 1;                }            }        }        return current_num;    }};
    

需要注意容易犯错的地方在于如果最后不做检查,很容易导致最后返回的是最后的值,而不会返回0.