用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)。

相关问题

请用C语言实现输入n个正整数,按照数字出现的顺序输出其中出现次数大于k的数字。

好的，以下是用C语言实现该算法的代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000

int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int main() {
    int n, k;
    int nums[MAX_N], count[MAX_N] = {0}, res[MAX_N], len = 0;

    printf("请输入n和k：\n");
    scanf("%d%d", &n, &k);

    printf("请输入%d个正整数：\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }

    qsort(nums, n, sizeof(int), cmp); // 排序

    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && nums[j] == nums[i]) {
            j++;
        }
        count[nums[i]] = j - i; // 记录每个数字出现的次数
        i = j - 1;
    }

    for (int i = 0; i < n; i++) {
        if (count[nums[i]] > k) { // 找出出现次数大于k的数字
            int j;
            for (j = 0; j < len; j++) {
                if (res[j] == nums[i]) {
                    break;
                }
            }
            if (j == len) { // 避免重复添加
                res[len++] = nums[i];
            }
        }
    }

    printf("出现次数大于%d的数字为：\n", k);
    for (int i = 0; i < len; i++) {
        printf("%d ", res[i]);
    }
    printf("\n");

    return 0;
}

首先，我们定义了一个`cmp`函数用于排序，然后读入`n`和`k`，以及`n`个正整数到`nums`数组中。接着，使用`qsort`函数对`nums`数组进行排序。

然后，我们遍历`nums`数组，记录每个数字出现的次数到`count`数组中。接着，再遍历`nums`数组，找出出现次数大于`k`的数字，并将其加入到结果数组`res`中，避免重复添加。

最后，输出结果数组`res`中的数字即可。

需要注意的是，由于本题中数字大小不超过1000，因此我们可以使用一个长度为1000的数组`count`来记录每个数字出现的次数。如果数字范围很大，需要使用哈希表等数据结构来记录。

用C语言实现题目：给定一个大小为 n 的数组，找到在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

一种简单的解决方法是使用哈希表。遍历整个数组，将每个元素作为键，将它们的出现次数作为值存储在哈希表中。最后再遍历一遍哈希表，找到出现次数大于 ⌊ n/2 ⌋ 的元素。

具体实现如下：

#include <stdio.h>
#include <stdlib.h>

#define HASH_SIZE 100

typedef struct node {
    int key;
    int count;
    struct node *next;
} Node;

int hash(int key) {
    return key % HASH_SIZE;
}

void insert(Node **hashTable, int key) {
    int index = hash(key);
    Node *p = hashTable[index];
    while (p != NULL) {
        if (p->key == key) {
            p->count++;
            return;
        }
        p = p->next;
    }
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->key = key;
    newNode->count = 1;
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

int findMajority(Node **hashTable, int n) {
    int threshold = n / 2;
    for (int i = 0; i < HASH_SIZE; i++) {
        Node *p = hashTable[i];
        while (p != NULL) {
            if (p->count > threshold) {
                return p->key;
            }
            p = p->next;
        }
    }
    return -1;
}

int main() {
    int n;
    printf("Enter the size of the array: ");
    scanf("%d", &n);
    int *a = (int *)malloc(sizeof(int) * n);
    printf("Enter the elements of the array: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    Node **hashTable = (Node **)malloc(sizeof(Node *) * HASH_SIZE);
    for (int i = 0; i < HASH_SIZE; i++) {
        hashTable[i] = NULL;
    }
    for (int i = 0; i < n; i++) {
        insert(hashTable, a[i]);
    }

    int majority = findMajority(hashTable, n);
    if (majority != -1) {
        printf("The majority element is %d\n", majority);
    } else {
        printf("There is no majority element\n");
    }

    return 0;
}

这里使用了一个简单的哈希函数，将键值取模，将余数作为哈希表的下标。在遍历数组时，将每个元素插入哈希表中。如果已经存在，则增加计数器；否则创建一个新的节点。在查找阶段，遍历哈希表，找到计数器大于阈值的节点即可。如果没找到，则说明没有出现次数大于 ⌊ n/2 ⌋ 的元素。