C语言乱序数组匹配问询：不可修改数组（禁止排序）

嘿，我看懂你的需求了——要判断两个无符号整数数组是不是彼此的乱序版本，还严格要求不能修改原数组（连排序都不行）。你的代码已经搭了个架子，但还没处理重复元素的问题，而且逻辑也没写完，我来帮你补全并优化这个实现。

首先得指出你现有代码的小漏洞：你现在只检查了a里的每个元素是否存在于b中，但如果数组里有重复元素，这个逻辑就会失效。比如a = [2,2,3]，b = [2,3,3]，你的代码会觉得每个a的元素都在b里，但实际上两个数组的元素重复次数不一样，根本不算匹配。

下面是完整的正确实现，我会给你逐段解释：

#include <stdio.h>

int scrambled(unsigned int a[], unsigned int b[], unsigned int len) {
    // 空数组直接视为匹配
    if (len == 0) {
        return 1;
    }

    // 用标记数组记录元素是否已被匹配，避免重复计数
    int matchedInB[len];
    int matchedInA[len];
    
    // 初始化标记数组为0（0代表未匹配）
    for (unsigned int i = 0; i < len; i++) {
        matchedInB[i] = 0;
        matchedInA[i] = 0;
    }

    // 第一步：检查a的每个元素都能在b中找到未被匹配的对应项
    for (unsigned int i = 0; i < len; i++) {
        int found = 0;
        for (unsigned int j = 0; j < len; j++) {
            // 找到相等且未被匹配的元素，就标记并跳出循环
            if (a[i] == b[j] && matchedInB[j] == 0) {
                found = 1;
                matchedInB[j] = 1;
                break;
            }
        }
        // 只要有一个元素找不到对应，直接返回不匹配
        if (!found) {
            return 0;
        }
    }

    // 第二步：严谨性检查——确保b的每个元素也能在a中找到对应（可选，但更稳妥）
    // 因为两个数组长度相同，第一步通过的话这步其实必然通过，不过多一层检查没坏处
    for (unsigned int i = 0; i < len; i++) {
        int found = 0;
        for (unsigned int j = 0; j < len; j++) {
            if (b[i] == a[j] && matchedInA[j] == 0) {
                found = 1;
                matchedInA[j] = 1;
                break;
            }
        }
        if (!found) {
            return 0;
        }
    }

    // 所有检查通过，返回匹配
    return 1;
}

// 测试用例，你可以直接跑起来验证
int main() {
    unsigned int arr1[] = {1, 2, 3, 2};
    unsigned int arr2[] = {2, 3, 1, 2};
    unsigned int arr3[] = {1, 2, 3, 4};

    printf("arr1和arr2是否匹配：%d\n", scrambled(arr1, arr2, 4)); // 输出1（匹配）
    printf("arr1和arr3是否匹配：%d\n", scrambled(arr1, arr3, 4)); // 输出0（不匹配）

    return 0;
}

关键逻辑说明 #

• 标记数组的作用：这是解决重复元素问题的核心。比如a里有两个2，我们在b里找到第一个2后就标记它为已匹配，下次再找2时就会跳过这个，去寻找下一个未被匹配的2，这样就能保证重复次数一致。
• 双重遍历的必要性：第一次遍历确保a的所有元素都能在b中找到对应，第二次遍历则是反向验证，虽然在长度相同的情况下第一次通过就足够，但多这一步能让函数在参数异常（比如传入不同len）时更鲁棒。
• 空数组处理：边界情况不能忘，空数组的乱序版本还是空数组，直接返回1即可。

这样实现完全符合你的要求——全程没有修改原数组，也没有用到排序，完美解决乱序数组的内容匹配问题。

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