C语言实现寻找数组第k小元素时出现Segmentation fault问题求助

问题需求 #

给定大小为n（1 ≤ n ≤ 1000000）的无序整数数组（含重复元素），找到第k小元素（升序排序后第k位元素，1 ≤ k ≤ n）。

我的解法与问题 #

我采用计数排序思路：先找出数组最大值，创建长度为max+1的数组统计每个元素出现次数，再遍历统计数组累加计数找到目标元素。但运行时出现Segmentation fault，调试未定位原因。

测试情况 #

• PTA平台：n=50时运行正常，n=80时失败；
• Code::Blocks环境：n=10000时出错，但该用例在PTA上正常。

输入输出格式 #

• 输入：第一行输入n和k，第二行输入n个整数；
• 输出：第k小元素。

示例输入：

10 4
2 3 5 12 4 9 3 8 2 9

示例输出：3

代码约束 #

• 代码长度≤16KB
• 运行时间≤400ms
• 内存限制≤64MB
• 栈空间≤8192KB

我的C代码 #

#include<stdio.h>

int main(void)
{
    int n, k;
    scanf("%d%d", &n, &k);
    int num[n];
    scanf("%d", &num[0]);
    int max = num[0];
    for (int i = 1; i < n; i++)
    {
        scanf("%d", &num[i]);
        if (num[i] > max)
        {
            max = num[i];
        }
    }
    int sort[max + 1];
    for (int i = 0; i < max + 1; i++)
    {
        sort[i] = 0;
    }
    for (int i = 0; i < n; i++)
    {
        sort[num[i]]++;
    }
    for (int i = 0, count = 0; i < max + 1; i++)
    {
        if (sort[i] != 0)
        {
            count += sort[i];
            if (count >= k)
            {
                printf("%d", i);
                break;
            }
        }
    }
    return 0;
}

Python测试用例生成脚本 #

import random

def generate_input(n, k):
    # 生成n个随机整数作为数组元素
    arr = [random.randint(1, 1000000) for _ in range(n)]

    # 将数组元素写入文件
    with open("input.txt", "w") as file:
        file.write(f"{n} {k}\n")
        file.write(" ".join(map(str, arr)))

# 生成符合问题条件的测试用例，例如n=10000，k=5000
generate_input(10000, 5000)

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