当前位置：首页 > article >正文

蓝桥杯算法日常|枚举[*找到最多的数]

article 2025/3/1 23:58:59

找到最多的数

重点疑问总结：

1、数组输入输出c++一般会采用那种方便的方式？？

用的就是我想的那种，就是用的最大范围定义的。

2、怎样方便给数组中每个数出现的次数计数？？

刚开始想的是：每个数把全部的数比较一下子

最后发现最佳方法是：哈希表，这里用了一个数组，数组下标表示统计的哪个数，数组的值是该数出现的次数。

题目截图

解题思路：

遍历矩阵，将每个数字及其出现次数存储在一个哈希表（这里使用数组模拟哈希表）中。
遍历哈希表，找到出现次数超过矩阵元素总数一半的数字。

C语言代码实现：

#include <stdio.h> 

// 定义矩阵最大行数和列数的常量
#define MAX_SIZE 1000 
#define MAX_NUM 1000 

int main() { 
    // 用于存储矩阵的行数和列数
    int n, m; 
    // 从标准输入读取矩阵的行数和列数
    scanf("%d %d", &n, &m); 

    // 定义二维数组（矩阵），其大小由输入的n和m决定
    int matrix[n][m]; 
    // 嵌套循环，外层循环遍历行，内层循环遍历列
    for (int i = 0; i < n; i++) { 
        for (int j = 0; j < m; j++) { 
            // 从标准输入读取矩阵每个元素的值
            scanf("%d", &matrix[i][j]); 
        } 
    } 

    // 定义哈希表（这里用数组模拟），用于统计每个数字出现的次数，初始化为0
    int hashTable[MAX_NUM] = {0}; 
    // 嵌套循环，遍历矩阵的每个元素
    for (int i = 0; i < n; i++) { 
        for (int j = 0; j < m; j++) { 
            // 对应数字在哈希表中的计数加1，表示该数字出现了一次
            hashTable[matrix[i][j]]++; 
        } 
    } 

    // 计算矩阵的总元素个数
    int totalElements = n * m; 
    // 遍历哈希表
    for (int i = 0; i < MAX_NUM; i++) { 
        // 如果某个数字出现的次数大于总元素个数的一半
        if (hashTable[i] > totalElements / 2) { 
            // 输出这个数字
            printf("%d\n", i); 
            // 程序结束并返回0，表示正常结束
            return 0; 
        } 
    } 

    // 如果没有找到符合条件（出现次数大于总元素个数一半）的数字，输出提示信息
    printf("No such number\n"); 
    return 0; 
}

上述代码首先读取矩阵的行数和列数，然后读取矩阵的元素。接着使用一个数组hashTable来统计每个数字出现的次数。最后遍历hashTable，找到出现次数超过矩阵元素总数一半的数字并输出。如果没有找到这样的数字，则输出No such number。

请注意，这里假设矩阵中的数字范围较小（不超过MAX_NUM），如果数字范围较大，可能需要使用更高效的哈希表数据结构，如unordered_map（如果使用C++）或其他更复杂的哈希实现（如果仅使用C）。此外，上述代码没有进行输入数据的合法性检查，在实际应用中可能需要添加相应的检查以确保程序的健壮性。

解题思路：

遍历矩阵，将每个元素放入一个unordered_map中，key为矩阵元素的值，value为该元素出现的次数。
遍历unordered_map，找到出现次数超过矩阵元素总数一半的元素并返回。

C++代码实现：

#include <iostream> 
#include <unordered_map> 
using namespace std; 

// 主函数，程序的入口点
int main() { 
    // 定义两个整数n和m，用于接收输入
    int n, m; 
    // 从标准输入读取n和m的值
    cin >> n >> m; 
    // 计算矩阵的总元素个数
    int totalElements = n * m; 
    // 创建一个无序映射（哈希表），用于存储数字及其出现的次数
    unordered_map<int, int> countMap; 
    // 外层循环，遍历n行
    for (int i = 0; i < n; i++) { 
        // 内层循环，遍历m列
        for (int j = 0; j < m; j++) { 
            // 定义一个整数num，用于接收输入的数字
            int num; 
            // 从标准输入读取一个数字
            cin >> num; 
            // 在countMap中查找num，如果不存在则插入并将其出现次数设为1，
            // 如果存在则将其出现次数加1
            countMap[num]++; 
        } 
    } 
    // 遍历countMap中的每一个键值对
    for (auto& pair : countMap) { 
        // 如果某个数字的出现次数大于总元素个数的一半
        if (pair.second  > totalElements / 2) { 
            // 输出这个数字
            cout << pair.first  << endl; 
            // 结束程序，返回0
            return 0; 
        } 
    } 
    // 如果没有找到出现次数大于总元素个数一半的数字，返回0
    return 0; 
}

上述代码首先读取矩阵的行数n和列数m，然后通过两层循环遍历矩阵，将每个元素放入unordered_map中统计出现次数。最后再次遍历unordered_map，找到出现次数超过一半的元素并输出。如果没有找到这样的元素，程序正常结束。

请注意，此代码假设输入的矩阵元素都是正整数，并且一定存在一个出现次数超过一半的数字。如果输入不满足这些条件，可能需要添加额外的错误处理代码。

查看全文

http://www.kler.cn/a/509051.html