C语言计算数组唯一元素总数超时优化求助（N、M≤1e6 内存受限）

你写的原有代码采用两层循环查重，时间复杂度为O(N²)，当N达到1e6规模时，总运算量超过1e12次，远远超出常规在线评测系统1秒可处理的1e8次运算上限，因此必然触发超时判定。
同时你代码中使用的变长数组arr[x]在N=1e6时会占用8MB左右内存（每个long占8字节），且存在栈溢出风险，也属于可优化点。

利用题目给出的「M是元素整数取值上限且M≤1e6」的约束，我们不需要使用字典/Map结构，直接开一个char类型的标记数组即可，1e6个char仅占用约1MB内存，完全符合内存限制：

• 初始化一个长度为M+1的char数组，所有元素初始值为0，代表对应数值未出现过
• 不需要存储全部输入数组，每读入一个数值就直接判断标记：
  • 如果标记为0，说明是第一次出现，计数器+1，同时把标记设为1
  • 如果标记为1，说明已经出现过，直接跳过
• 最终输出计数器的值即可

优化后时间复杂度降到O(N)，1e6次运算可以轻松在1秒内完成，内存占用也远低于限制。

#include <stdio.h>

// 全局数组默认初始化为0，且不会占用栈空间，避免栈溢出
char visited[1000001];

int main(){
    int n, num, cnt = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &num);
        if(!visited[num]){
            cnt++;
            visited[num] = 1;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

如果题目允许动态开数组，也可以根据读入的M动态申请空间，进一步压缩内存占用。

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