数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。以C++

语言实现：

int majorityElement(int* nums, int numsSize){
int count = 1;
int majority = nums[0];
for(int i = 1; i < numsSize; i++){
if(nums[i] == majority){
count++;
}else{
count--;
if(count == 0){
majority = nums[i+1];
}
}
}
return majority;
}

算法思路：

使用一个计数器 count 和一个记录当前多数元素的变量 majority，遍历数组，如果当前元素与 majority 相同，则将计数器加 1，否则将计数器减 1。当计数器减为 0 时，将 majority 设为下一个元素。因为多数元素出现的次数超过一半，所以遍历完整个数组后，majority 就是答案。时间复杂度为 O(n)，空间复杂度为 O(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