出现次数超过一半(50%)的数

第一步: 思路分析

本题要求我们找出出现次数超过一半的数，可以采用摩尔投票法进行求解。摩尔投票法的思路是，每次从数组中取出两个不同的数之后，将它们同时删除，直到数组中只剩下一个数或者多个相同的数。此时剩下的就是出现次数超过一半的数。

第二步: 代码实现

采用摩尔投票法实现代码如下：

int majorityElement(vector<int>& nums) {
    int count = 1;
    int majority = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        if (count == 0) {
            majority = nums[i];
            count = 1;
        } else if (majority == nums[i]) {
            count++;
        } else {
            count--;
        }
    }
    return majority;
}

第三步：时间复杂度分析

由于采用了摩尔投票法，每次遍历数组的时间复杂度为O(n)，因此总的时间复杂度为O(n)。

第四步：编写测试用例

下面提供两条测试用例：

• 输入：[1,2,3,2,2]，输出：2
• 输入：[1,2,1,1,4]，输出：1

以上就是本题的完整攻略。