计算数组中所有元素的频率

Question

问题:给定一个由 n 个整数组成的未排序数组，其中可以包含从 1 到 n 的整数。某些元素可以重复多次，而其他一些元素可以不存在于数组中。计算所有存在元素的频率并打印缺失的元素

代码:

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

int main() {
    int i, j, x, t, n, m;

    scanf("%d", &t);
    while (t--) {
        scanf("%d",&m);
        int b[m];
        int a[m];
        int c[m];

        for(i = 0; i < m; i++) {
            scanf("%d", &a[i]);
        }
        for (i = 0; i < m; i++) {
            b[i] = i + 1;
        }
    //  for (i = 0; i < m; i++)
        //{
        //  printf("%d ", b[i]);
        //}
        for (i = 0; i < m; i++) {
            c[i] = 0;
        }
        for (i = 0; i < m; i++) {
            for (j = 0; j < m; j++) {
                if (b[j] == a[i]) {
                    c[i] = c[i] + 1;
                }
            }
        }
        for (i = 0; i < m; i++) {
            printf("%d ", c[i]);
        }
    }
}

问题:我得到的输出为 1 1 1 1 1。有人可以指出我代码中的逻辑错误吗？

Answer 1

问题在于您使用 i 而不是 j 设置看到的数字。

    for (i = 0; i < m; i++) {
        for (j = 0; j < m; j++) {
            if (want[j] == input[i]) {
                seen[i] = seen[i] + 1;  // HERE
            }
        }
    }

如果输入2 2 2，则当i为0时匹配。当i为1时匹配。并且当 i 为 2 时它将匹配。因此每个位置都会得到 1。 i 是看到的数字的位置。相反，您想要增加 j，即正在检查的数字 - 1。

    for (i = 0; i < m; i++) {
        for (j = 0; j < m; j++) {
            if (want[j] == input[i]) {
                seen[j] = seen[j] + 1;
            }
        }
    }

这指出了一种使整个事情变得更加高效的方法。 想要不是必需的。由于我们想要从 1 到 n 的数字，因此我们可以使用 seen 的数组索引 + 1。而且您不需要每次都重新扫描整个数组，seen 可以在您读取时构建起来。

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

int main() {
    int size;
    scanf("%d",&size);

    int seen[size];
    int input;

    // Initialize seen
    for(int i = 0; i < size; i++) {
        seen[i] = 0;
    }

    // Read input and store how many integers we've seen
    for(int i = 0; i < size; i++) {
        scanf("%d", &input);
        seen[input-1] += 1;
    }

    // Print the counts
    for (int i = 0; i < size; i++) {
        printf("%d: %d ", i+1, seen[i]);
    }
    puts("");
}