如何解决C语言中约束为10e9时出现的Memory Limit内存超限问题

• 你声明的int data[arr]长度为10^9，单个int占4字节，总内存占用约为3.7GB，远超过常规编程竞赛/在线测评的内存限制（通常为256MB~1GB）。
• 该数组是栈上的变长数组（C99特性），而系统默认栈空间仅为8MB左右，哪怕数组长度只有2e6都会直接爆栈，不需要到1e9的规模。
• 代码中包含两次O(1e9)的遍历逻辑，哪怕内存足够也会触发时间超限错误。

1. 替换全量数组为哈希表/离散化映射 #

你实际只会用到输入的t个数值的计数，完全不需要开覆盖1e9范围的全量数组：

• 可以直接用C语言的uthash（仅头文件的轻量哈希库，无需额外安装）存储出现过的数值和对应计数，空间复杂度直接降到O(t)，t为每组测试用例的输入数量，一般都在1e5以内，完全不会超内存。
• 也可以选择离散化方案：提前收集所有输入的数值，排序去重后映射到0~t-1的连续下标，再开长度为t的数组计数，效果和哈希表一致。

2. 废弃全量遍历逻辑 #

原来两次遍历1e9长度数组的逻辑可以直接删掉：

• 每组测试用例处理完后清空哈希表即可，不需要初始化全量空间。
• 计数过程中可以同步维护当前最高出现次数、以及对应的最小数值，不需要后续遍历所有值计算结果，时间复杂度直接降到O(t)。

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

// 哈希表结构体定义
typedef struct {
    int key; // 存储输入的数值
    int count; // 存储对应出现次数
    UT_hash_handle hh;
} HashItem;

int main() {
    int n, t, a;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        HashItem *hash = NULL, *item;
        int max_count = 0, min_key = 1e9 + 1;
        scanf("%d", &t);
        for(int j = 0; j < t; j++) {
            scanf("%d", &a);
            // 查找当前数值是否已存在于哈希表
            HASH_FIND_INT(hash, &a, item);
            if(item == NULL) {
                item = malloc(sizeof(HashItem));
                item->key = a;
                item->count = 1;
                HASH_ADD_INT(hash, key, item);
            } else {
                item->count++;
            }
            // 同步维护最高频次和对应的最小数值
            if(item->count > max_count) {
                max_count = item->count;
                min_key = a;
            } else if(item->count == max_count && a < min_key) {
                min_key = a;
            }
        }
        printf("Case #%d: %d\n%d\n", i+1, max_count, min_key);
        // 清空当前组哈希表，避免影响下一组计算
        HashItem *tmp;
        HASH_ITER(hh, hash, item, tmp) {
            HASH_DEL(hash, item);
            free(item);
        }
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者Calvin