给你n个数，有一个数的出现次数超过一半，请找出这个数。

这道题目可以使用摩尔投票算法来解决。具体思路是从第一个数开始遍历，将其作为候选数，然后遍历后面的数，如果遇到相同的数，则计数器加1，否则计数器减1。当计数器减为0时，将当前数作为候选数。最后剩下的候选数就是出现次数超过一半的数。

需要注意的是，如果给定的n个数中没有出现次数超过一半的数，那么最后剩下的候选数不一定是出现次数最多的数，需要再次遍历验证一下。

以下是摩尔投票算法的代码实现：

int majorityElement(vector<int>& nums) {
    int candidate = 0;
    int count = 0;
    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }
    count = 0;
    for (int num : nums) {
        if (num == candidate) {
            count++;
        }
    }
    return (count > nums.size() / 2) ? candidate : -1;
}

相关问题

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

解法1：哈希表

遍历数组，用哈希表记录每个数字出现的次数，如果某个数字出现的次数超过数组长度的一半，就返回该数字。

时间复杂度：O(n)

空间复杂度：O(n)

解法2：排序

将数组排序，由于该数字出现的次数超过数组长度的一半，所以该数字一定是数组的中间元素。

时间复杂度：O(nlogn)

空间复杂度：O(1)

解法3：摩尔投票法

遍历数组，用一个计数器记录当前数字出现的次数，如果遇到相同的数字，计数器加1，否则计数器减1。如果计数器变为0，就将下一个数字作为候选数字。最后留下的候选数字就是出现次数超过数组长度一半的数字。

时间复杂度：O(n)

空间复杂度：O(1)

Python代码：

c++分治法求数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

解法一：排序法

先将数组排序，由于该数字出现的次数超过数组长度的一半，所以排序后中间的数一定是该数字。

时间复杂度：O(nlogn)

解法二：哈希表法

遍历数组，将每个数字出现的次数存入哈希表中，最后遍历哈希表找到出现次数超过数组长度一半的数字。

时间复杂度：O(n)，但需要额外的空间来存储哈希表。

解法三：摩尔投票法

由于该数字出现的次数超过数组长度的一半，所以可以使用一个计数器和一个候选数字，遍历数组，如果当前数字与候选数字相同，则计数器加1，否则计数器减1，如果计数器为0，则更新候选数字为当前数字。最后剩下的候选数字即为结果。

时间复杂度：O(n)

以下是摩尔投票法的Python代码实现：

def majorityElement(nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate