如何判断元素无序可重复的多个int数组等价并输出对应数组名

核心思路：判断两个数组元素等价（无序、可重复），本质是元素的频率分布完全一致。无需逐个比对索引，可通过以下两种简洁方案实现：

方案一：排序比对法（通用、易实现） #

将每个数组的有效元素排序后，直接比对排序结果是否完全一致——等价数组排序后的顺序和元素分布必然完全相同。

完整代码实现 #

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

// qsort 所需的整数比较函数
int cmp_int(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

// 判断两个数组是否元素等价
int are_arrays_equivalent(int *arr1, int len1, int *arr2, int len2) {
    if (len1 != len2) return 0; // 长度不同直接排除
    
    // 分配临时数组存储排序结果，避免修改原数组
    int *sorted1 = malloc(len1 * sizeof(int));
    int *sorted2 = malloc(len2 * sizeof(int));
    if (!sorted1 || !sorted2) {
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    
    memcpy(sorted1, arr1, len1 * sizeof(int));
    memcpy(sorted2, arr2, len2 * sizeof(int));
    
    qsort(sorted1, len1, sizeof(int), cmp_int);
    qsort(sorted2, len2, sizeof(int), cmp_int);
    
    // 比对排序后的数组
    int result = memcmp(sorted1, sorted2, len1 * sizeof(int)) == 0;
    
    free(sorted1);
    free(sorted2);
    return result;
}

int main() {
    // 用结构体统一管理数组的名称、指针和有效长度
    typedef struct {
        const char *name;
        int *arr;
        int len;
    } ArrayInfo;
    
    // 示例数组
    int arr1[] = {3, 41, 315, 2};
    int arr2[] = {5, 31, 315};
    int arr3[] = {315, 41, 3, 2, 2, 41};
    
    ArrayInfo arrays[] = {
        {"First", arr1, sizeof(arr1)/sizeof(arr1[0])},
        {"Second", arr2, sizeof(arr2)/sizeof(arr2[0])},
        {"Third", arr3, sizeof(arr3)/sizeof(arr3[0])}
    };
    int arr_count = sizeof(arrays)/sizeof(arrays[0]);
    
    // 标记已处理的数组，避免重复输出
    int processed[arr_count];
    memset(processed, 0, sizeof(processed));
    
    // 遍历分组输出等价数组
    for (int i = 0; i < arr_count; i++) {
        if (processed[i]) continue;
        
        printf("%s", arrays[i].name);
        processed[i] = 1;
        
        for (int j = i+1; j < arr_count; j++) {
            if (are_arrays_equivalent(arrays[i].arr, arrays[i].len, arrays[j].arr, arrays[j].len)) {
                printf(" %s", arrays[j].name);
                processed[j] = 1;
            }
        }
        printf("\n");
    }
    
    return 0;
}

方案优势 #

• 依赖C标准库函数qsort和memcmp，代码简洁可读性高
• 自动处理无序、重复元素的场景
• 通过结构体管理有效长度，解决了原代码中固定N导致的默认初始化元素干扰问题

方案二：频次统计法（高性能，适合元素范围明确的场景） #

如果已知数组元素的范围（比如非负整数且最大值有限），可以统计每个元素的出现次数，对比频次分布是否完全一致。

代码示例 #

// 假设元素最大值不超过1000
int are_arrays_equivalent_freq(int *arr1, int len1, int *arr2, int len2) {
    if (len1 != len2) return 0;
    
    int freq[1001] = {0}; // 初始化频次数组
    
    // 统计第一个数组的元素频次
    for (int i = 0; i < len1; i++) {
        freq[arr1[i]]++;
    }
    
    // 用第二个数组抵消频次，中途出现负数直接返回不等价
    for (int i = 0; i < len2; i++) {
        freq[arr2[i]]--;
        if (freq[arr2[i]] < 0) return 0;
    }
    
    // 检查所有元素频次是否归零
    for (int i = 0; i <= 1000; i++) {
        if (freq[i] != 0) return 0;
    }
    return 1;
}

方案优势 #

• 时间复杂度为O(n)，比排序法的O(n log n)性能更高
• 无需分配临时内存，内存开销更小

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