查找数组中元素的最高频率（有时有效）

Question

您好，我运行下面的代码存在一个小问题。有时返回的最大频率是正确的，但有时不是。当错误发生时它总是 returns 1 太多了。我似乎找不到错误。我试图编写第一个循环 nrofpeople-1 但它没有什么区别。

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

#define MAX 10000

int main(int argc, const char *argv[]) {
    int nrofpeople;
    int array[MAX];
    int num = 0;
    int index;

    srand((unsigned int)time(NULL));

    printf("How many people?");
    scanf("%d", &nrofpeople);

    for (int i = 0; i < nrofpeople; i++) {
        array[i] = rand() % 3 + 1; // generate random number to test
    }

    int maxcount = 0;
    for (int i = 0; i < nrofpeople; i++) {
        index = 1;

        for (int j = 1; j < nrofpeople; j++) {
            if (array[i] == array[j]) {
                index++;
            }
        }
        if (index > maxcount) {
            maxcount = index;
            num = array[i];
        }
    }

    printf("Number: %d Occurred: %d times\n", num, maxcount);
    return 0;
}

Answer 1

(sometimes it works)

我真的很惊讶它能奏效。在任何情况下，如果你想在你的输入数组中找到最大的条目，你可以通过一次传递来实现：

int maxcount = 0;

for (int i=0; i < nrofpeople; i++)
{
    if (array[i] > maxcount)
    {
        maxcount = array[i];
    }
}

您目前正在数组上使用双循环，如果您需要对数组进行叉积样式比较，这将是合适的。但这似乎与你的问题陈述不一致。

Answer 2

如果您打算查找给定数组中每个数字的频率，您可以制作另一个数组，其中包含原始数组包含的所有元素减去重复的数字。然后你可以设置一个计数数组来统计原始数组中所有数字的频率。

    int flag = 0, a[nrpeople], k = 0;
    for(int i = 0; i < nrpeople; i++){
    flag = 0;
    for(int j = i+1; j<nrpeople; j++){
        if(array[i] == array[j]){
            flag = 1;
            break;
        }
    }
    if(flag == 0){
        a[k] = array[i];
        k++;
    }
    }
    int count[k] = {0};
    for(int i=0; i<k; i++){
    for(int j = 0; j<nrpeople; j++){
        if(a[i] == array[j])
        count[i]++;
    }
    }

然后用计数数组做任何你想做的事。

Answer 3

您所要解决的问题的表述中有一些地方没有清楚。我想如果你能给我们提供几个例子（输入+预期输出）会更好。

无论如何，我读了你最后的评论，你似乎想在给定数组中找到最常见（频繁）的元素。这是实现这一目标的方法。代码中有注释，请仔细阅读。

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

#define MAX 10

// gcc main.c -o main -std=c99
// ./main

int main(int argc, const char * argv[])
{
    srand((unsigned int)time(NULL));

    int array[MAX];
    for(int i=0; i<MAX; i++) {
        array[i] = -1; // to make sure there are no uninitialized fields
    }

    int npeople = -1;
    do {
        printf("How many people (1 to %d)? ", MAX);
        scanf("%d", &npeople);
    }
    while(npeople<1 || npeople>MAX);

    // Filling array with integer values in range [min, max]

    const unsigned int min=5;
    const unsigned int max=15;
    for(int i=0; i<npeople; i++) {
        array[i] = min + rand() % (max-min+1);
    }

    // Now searching for the most frequent element

    const int f = max+1;
    int freq[f];
    /* frequency array
     * freq[i] = k means value i appears k times in array
     * And to make things easier, we use up to max+1 fields for the frequency array.
     * But normally, only max-min+1 fields are needed.
     * However in that case, additional conversions (between array and freq)
     * become mandatory.
     */

    // initialization
    for(int i=0; i<f; i++) {
        freq[i] = 0;
    }

    // filling frequency array
    for(int i=0; i<MAX; i++) {
        freq[array[i]]++;
    }

    // Display

    printf("\n");
    printf("Input array\n");
    printf("===========\n");
    for(int i=0; i<MAX; i++) {
        printf("%d", array[i]);
        i==MAX-1 ? printf("\n") : printf(" ");
    }

    printf("\n");
    printf("Frequency array\n");
    printf("===============\n");
    for(int i=0; i<f; i++) {
        printf("%0d", freq[i]);
        i==f-1 ? printf("\n") : printf(" ");
    }

    printf("\n");
    printf("Note\n");
    printf("====\n");
    printf("freq[i] = k MEANS value i appears k times in array\n");

    int mse = -1; // most frequent element
    int h = -1; // highest occurrence
    for(int i=0; i<f; i++) {
        if(freq[i] > h) {
            h = freq[i];
            mse = i;
        }
    }
    printf("\n");
    printf("Conclusion\n");
    printf("==========\n");
    printf("The most frequent element is %d, appearing %d time(s).\n", mse, h);

    return 0;
}

此算法有效，因为我们知道数组中的最小值和最大值。如果我们不这样做，我们可以先使用 qsort 对数组进行排序，然后我们将能够找到数组的 extrema（极值）。

希望对您有所帮助。

Answer 4

您的代码中存在一些问题：

您没有检查输入人数的有效性，导致无效输入出现未定义行为。
您查找最高频率的算法存在缺陷：您为 i > 0 计算了两次 array[i]。实际上，您可以使内部循环检查更少的条目，只检查给定数字的第一次出现产生最大计数。

这是一个改进的版本：

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

#define MAX 10000

int main(int argc, const char *argv[]) {
    int nrofpeople;
    int array[MAX];

    printf("How many people?");
    if (scanf("%d", &nrofpeople) != 1 || nrofpeople <= 0 || nrofpeople > MAX) {
        printf("invalid number of people\n");
        return 1;
    }

    srand((unsigned int)time(NULL));
    for (int i = 0; i < nrofpeople; i++) {
        array[i] = rand() % 3 + 1; // generate random number to test
    }

    int num = 0, maxcount = 0;
    for (int i = 0; i < nrofpeople; i++) {
        int count = 1;
        for (int j = i + 1; j < nrofpeople; j++) {
            if (array[i] == array[j]) {
                count++;
            }
        }
        if (count > maxcount) {
            maxcount = count;
            num = array[i];
        }
    }
    printf("Number: %d Occurred: %d times\n", num, maxcount);
    return 0;
}

查找数组中元素的最高频率（有时有效）

Finding highest frequency of an element in an array (sometimes it works)

c

loops

frequency