C语言编程给定一个数组,找出一个出现次数大于n/2的数

可以使用摩尔投票算法（Moore Voting Algorithm）来解决这个问题，时间复杂度为O(n)。

算法步骤如下：

1. 初始化候选数为数组的第一个数，计数器为1。
2. 遍历数组，如果当前的数等于候选数，则计数器加1，否则计数器减1。
3. 如果计数器减为0，则重新选择下一个数作为候选数，计数器重置为1。
4. 最后留下来的候选数就是出现次数大于n/2的数。

下面是C语言的实现代码：

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

注意：这个算法假设输入的数组中一定存在出现次数大于n/2的数，如果不存在，则需要增加一些判断。

相关问题

n个数里出现次数大于等于n/2的数 C语言

可以使用摩尔投票算法来解决这个问题，时间复杂度为 O(n)。具体思路如下：

1. 假设第一个数为众数，计数器为1。
2. 遍历数组，如果下一个数与当前数相同，则计数器加1；否则计数器减1。
3. 如果计数器归零，则将下一个数设为众数。
4. 最后得到的众数即为所求。

下面是具体的 C 代码实现：

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

c语言 给定一个数组，求出其中连续的最大的和：

A：可以使用动态规划来解决该问题，具体步骤如下：

1. 定义一个数组dp，其中dp[i]表示以第i个元素结尾的子数组的最大和。

2. 初始化dp[0]为数组中的第一个元素，遍历数组，计算出dp[i]的值，其中dp[i]可以由以下两种情况得到：

a. dp[i-1]+nums[i]，表示将当前元素加入之前的子数组中。

b. nums[i]，表示当前元素单独作为一个子数组。

3. 在遍历数组的过程中，同时记录最大的dp[i]，即为所求的连续最大和。

以下是具体实现代码：

int maxSubArray(int* nums, int numsSize){
    int dp[numsSize];   //定义dp数组
    dp[0] = nums[0];    //初始化dp[0]
    int maxSum = dp[0]; //初始化最大和为dp[0]
    for (int i = 1; i < numsSize; i++) {
        dp[i] = (dp[i-1] > 0) ? dp[i-1] + nums[i] : nums[i]; //计算dp[i]
        maxSum = (dp[i] > maxSum) ? dp[i] : maxSum;   //更新最大和
    }
    return maxSum;  //返回最大和
}