使用quicksort实现坐标去重时大输入场景出现运行时错误排查

这一问题是代码错误导致，和编译器无关，具体错误点如下：

• 固定大小数组越界：你定义的存储x坐标的数组x大小仅为1000，当测试用例数量较多、或单个用例的d值较大时，总坐标数量ct会超过1000，写入数组时越界触发运行时错误。你可以根据实际输入的总坐标数动态申请内存，或者预先把数组开至足够大的容量。
• count函数访问越界：count函数的循环条件为i < ct，当i取值为ct-1时，会访问A[i+1]也就是A[ct]，超出了数组下标0到ct-1的合法范围，属于未定义行为。修复时可以把循环条件改为i < ct-1，计数完成后额外加1即可得到正确的去重数量。
• 输入类型不匹配：你将tmp、y、d定义为long int类型，但调用scanf时使用的是适配int的%d格式符，类型不匹配会导致输入读取错误，触发未定义行为。你可以将三个变量改为int类型，或者把格式符替换为适配long int的%ld。
• 输入格式适配错误：示例给出的输入是逗号分隔的4,9,2，但你使用的"%d%d%d"格式符仅支持空白分隔的输入，遇到逗号会读取失败，导致变量赋值错误。如果测试用例输入是逗号分隔，需要将格式串改为"%d,%d,%d"。
• 逻辑疏漏：你的代码完全忽略了y坐标的影响，如果测试用例中存在不同y值的区间，仅对x坐标去重会把(x,y1)和(x,y2)两个不同坐标误判为同一个，导致统计结果错误。需要将x和y组合为唯一标识后再去重。
• 算法不符合要求：题目要求使用归并排序实现，但你当前代码使用的是快速排序，不符合要求的话也会导致判题失败。

修复后的参考代码：

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

// 归并排序实现，符合题目要求
void merge(int *arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int *L = (int*)malloc(n1 * sizeof(int));
    int *R = (int*)malloc(n2 * sizeof(int));
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    free(L);
    free(R);
}

void merge_sort(int *arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int count(int A[], int ct) {
    if (ct == 0) return 0;
    int cnt = 1;
    for (int i = 0; i < ct - 1; ++i) {
        if (A[i] != A[i + 1]) cnt++;
    }
    return cnt;
}

int main() {
    int t;
    scanf("%d", &t);
    long int tmp, y, d;
    int ct = 0;
    // 第一次遍历统计总坐标长度
    long int *temp_input = (long int*)malloc(t * 3 * sizeof(long int));
    for (int l = 0; l < t; ++l) {
        scanf("%ld,%ld,%ld", &tmp, &y, &d);
        temp_input[l*3] = tmp;
        temp_input[l*3+1] = y;
        temp_input[l*3+2] = d;
        ct += d + 1;
    }
    // 动态申请足够大的数组
    int *x = (int*)malloc(ct * sizeof(int));
    int j = 0;
    for (int l = 0; l < t; ++l) {
        tmp = temp_input[l*3];
        d = temp_input[l*3+2];
        for (int i = 0; i <= d; ++i) {
            x[j++] = tmp + i;
        }
    }
    free(temp_input);
    merge_sort(x, 0, ct - 1);
    int cnt = count(x, ct);
    printf("%d\n", cnt);
    free(x);
    return 0;
}

注：以上代码默认所有测试用例的y坐标一致，若存在不同y值需要调整存储结构，同时存储x和y后再去重。

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