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

可以使用计数排序的思想，时间复杂度为 O(n)。具体思路如下：

1. 遍历数组，统计每个数出现的次数，存储在一个桶中。
2. 遍历桶，找到出现次数大于等于 n/2 的数。
3. 如果找到了，则返回这个数；否则返回 -1，表示不存在这样的数。

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

int majorityElement(int* nums, int numsSize) {
    int max_num = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] > max_num) {
            max_num = nums[i];
        }
    }

    int *bucket = (int *)calloc(max_num + 1, sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        bucket[nums[i]]++;
    }

    int half_num = numsSize / 2;
    for (int i = 0; i <= max_num; i++) {
        if (bucket[i] >= half_num) {
            return i;
        }
    }

    return -1;
}

需要注意的是，这个实现假设输入的数都是非负整数。如果输入的数可能包含负数，则需要对桶的大小进行相应的调整。

相关问题

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语言，不用摩尔投票，不用哈希表， 写n个数里出现次数大于等于n/2的数

可以使用 Boyer-Moore 投票算法来解决这个问题。该算法的基本思想是，维护一个候选众数和一个计数器，初始时候候选众数为第一个数，计数器为1，遍历数组，如果当前数等于候选众数，则计数器加1，否则计数器减1，如果计数器为0，则将当前数设为候选众数，计数器重新设为1，最终候选众数就是数组中出现次数大于等于n/2的数。

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

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

这段代码的时间复杂度为 O(n)，空间复杂度为 O(1)。