数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。以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)。

相关问题

给你一个非空数组nums，找出此数组中的最大数。 c语言实现

可以使用循环遍历数组，依次比较每个数与当前最大值的大小，更新最大值。具体代码如下：

#include <stdio.h>

int main() {
    int nums[] = {3, 9, 2, 5, 1, 8};
    int len = sizeof(nums) / sizeof(nums[0]);  // 数组长度
    int max_num = nums[0];  // 假设第一个数为最大值

    for (int i = 1; i < len; i++) {  // 从第二个数开始遍历
        if (nums[i] > max_num) {  // 如果当前数比最大值大
            max_num = nums[i];  // 更新最大值
        }
    }

    printf("最大数为：%d\n", max_num);

    return 0;
}

输出结果为：

最大数为：9

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

给定一个非空整数数组 `nums`，找到其中的那个元素，它在数组中出现了超过长度的一半即 `n / 2` 次。由于题目保证了数组中存在唯一的一个多数元素，所以我们可以利用这个特性来找出它。一种常见的解决方案是使用哈希表（或称为字典）来统计每个元素出现的次数。遍历数组，对于每一个元素，如果它还没有在哈希表中，就添加并将计数设置为1；如果已经存在，则将计数加1。当遍历结束后，哈希表中出现次数最多的元素就是我们要找的多数元素。

算法步骤大致如下：
1. 初始化一个空的哈希表。
2. 遍历数组 `nums`，对于每个元素，检查其在哈希表中的计数并更新。
3. 最后，查找哈希表中计数最大的元素，这就是多数元素。

以下是 Python 的示例代码：

def majorityElement(nums):
    count = {}
    for num in nums:
        if num not in count:
            count[num] = 1
        else:
            count[num] += 1
    return max(count, key=count.get)