询问统计(关键词-hash)c++解题

Question

​
题目描述
输入 n 个正整数 ai​，利用hash方法对这些数据进行统计。

q 次询问，每次查询一个数字 x ，请回答 x 在这 n 个数中出现的次数。

输入格式
第一行：两个正整数 𝑛 (𝑛≤100000)n (n≤100000) 和 𝑞 (𝑞≤100000)q (q≤100000)

第二行： n 个正整数 𝑎𝑖 (𝑎𝑖≤1000)ai​ (ai​≤1000)

第三行； q 个正整数 𝑥 (𝑥≤1000)x (x≤1000)

输出格式
输出 q 行，每行一个整数。若 x 在 n 个数中没有出现过，输出 00 。

样例 #1
样例输入 #1
10 3
1 2 1 2 3 2 1 3 1 1
1
3
4

样例输出 #1
5
2
0

 
​

Answer 1

该回答引用自GPT-deepseek, 由博主 GISer Liu 编写：

好的，我们来详细分析并解决这个问题。

问题分析

用户需要实现一个程序，该程序能够：

1. 读取输入的 n 个正整数 ai。
2. 使用哈希方法对这些数据进行统计。
3. 处理 q 次查询，每次查询一个数字 x，并输出 x 在这 n 个数中出现的次数。

解决方案

我们可以使用一个哈希表（在C语言中可以使用数组来模拟）来记录每个数字出现的次数。具体步骤如下：

1. 读取输入的 n 和 q。
2. 读取 n 个正整数 ai，并使用一个数组来记录每个数字出现的次数。
3. 读取 q 个查询数字 x，并输出每个数字在 n 个数中出现的次数。

代码实现

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

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

#define MAX_NUM 1001  // 因为 ai 最大为 1000，所以数组大小为 1001

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

    int count[MAX_NUM] = {0};  // 初始化数组，用于记录每个数字出现的次数

    // 读取 n 个正整数 ai，并统计每个数字出现的次数
    for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);
        count[num]++;
    }

    // 处理 q 次查询
    for (int i = 0; i < q; i++) {
        int x;
        scanf("%d", &x);
        printf("%d\n", count[x]);
    }

    return 0;
}

代码解释

1. 定义常量和数组：

   #define MAX_NUM 1001
   int count[MAX_NUM] = {0};
   

   这里定义了一个大小为 1001 的数组 count，用于记录每个数字出现的次数。初始化为 0。

2. 读取输入：

   scanf("%d %d", &n, &q);
   

   读取 n 和 q 的值。

3. 统计数字出现次数：

   for (int i = 0; i < n; i++) {
       int num;
       scanf("%d", &num);
       count[num]++;
   }
   

   读取 n 个正整数 ai，并使用数组 count 记录每个数字出现的次数。

4. 处理查询：

   for (int i = 0; i < q; i++) {
       int x;
       scanf("%d", &x);
       printf("%d\n", count[x]);
   }
   

   读取 q 个查询数字 x，并输出每个数字在 n 个数中出现的次数。

总结

通过使用一个数组来记录每个数字出现的次数，我们可以高效地处理查询操作。这个方法的时间复杂度为 O(n + q)，在给定的数据范围内是可行的。

希望这个解决方案能够满足您的需求。如果有任何问题或需要进一步的解释，请随时告诉我！

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑