不排序求数组中位数的C程序问题：重复元素场景失效求助

原程序在无重复元素的数组中能正确找到中位数，但遇到重复元素时逻辑失效，核心问题是忽略了等于基准值（piv）的元素对位置判断的影响，以下是修正后的实现及思路：

问题分析 #

原代码仅统计比piv大或小的元素，当存在重复元素时，中间位置的元素可能被多个相同值占据，原判断条件（如奇数长度要求lower == higher）过于严格，无法匹配重复场景。

修正后的代码 #

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

int median_finder(int size, int* data) {
    int n1 = -1, n2 = -1;
    // 奇数长度的目标位置：第k小的元素（k从0开始）
    int odd_target = (size - 1) / 2;
    // 偶数长度的两个目标位置
    int even_target1 = size / 2 - 1;
    int even_target2 = size / 2;

    for (int t = 0; t < size; t++) {
        int piv = data[t];
        int lower = 0; // 小于piv的元素数
        int equal = 0; // 等于piv的元素数
        int higher = 0; // 大于piv的元素数

        for (int j = 0; j < size; j++) {
            if (data[j] < piv) {
                lower++;
            } else if (data[j] == piv) {
                equal++;
            } else {
                higher++;
            }
        }

        if (size % 2 != 0) {
            // 奇数长度：piv的覆盖区间包含目标位置
            if (lower <= odd_target && lower + equal > odd_target) {
                printf("MEDIAN: %d\n", piv);
                return 0;
            }
        } else {
            // 偶数长度：检查piv是否覆盖第一个目标位置
            if (lower <= even_target1 && lower + equal > even_target1 && n1 == -1) {
                n1 = piv;
            }
            // 检查piv是否覆盖第二个目标位置
            if (lower <= even_target2 && lower + equal > even_target2 && n2 == -1) {
                n2 = piv;
            }

            // 找到两个候选值后计算中位数
            if (n1 != -1 && n2 != -1) {
                int median = (n1 + n2) / 2;
                printf("Median: %d\n", median);
                return 0;
            }
        }
    }

    // 极端情况处理（如空数组，实际输入不会触发）
    printf("No median found\n");
    return -1;
}

int main(int argc, char** argv) {
    if (argc < 2) {
        printf("Usage: %s <size> <num1> <num2> ...\n", argv[0]);
        return 1;
    }
    int size = atoi(argv[1]);
    if (size <= 0) {
        printf("Invalid size\n");
        return 1;
    }
    int data[size];
    for (int i = 0; i < size; i++) {
        data[i] = atoi(argv[2 + i]);
    }
    median_finder(size, data);
    return 0;
}

关键修改说明 #

• 新增equal计数：统计与piv相等的元素，明确piv在数组中的覆盖区间（[lower, lower+equal)）
• 奇数长度判断逻辑：只要目标位置（(size-1)/2）落在piv的覆盖区间内，piv就是中位数，无需严格满足lower == higher
• 偶数长度逻辑修正：分别检查两个目标位置是否被piv的覆盖区间包含，且确保每个候选值只被记录一次（避免重复元素多次触发计数）
• main函数健壮性优化：增加参数合法性检查，避免非法输入导致崩溃

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