C语言中如何校验n×n矩阵内是否存在重复数值

现有代码缺陷说明 #

• 仅比对同行、同列的相邻元素，自然无法检测非相邻、跨行列的重复值
• 存在数组越界风险：当j遍历到n-1时，matrix[i][j+1]会访问到数组边界外的内存，列循环的matrix[i+1][j]存在同样问题
• isEqual变量每次判断都会被覆盖，即便检测到重复，下一次不相等的判断会直接把标记重置为0，最终无法正确留存是否存在重复的结果

可选解决方案 #

方案1：暴力循环比对（适用于n较小的场景，时间复杂度O(n⁴)，无需额外空间） #

遍历每个元素，和它之后的所有元素逐一比较，只要发现相等就标记重复并终止校验，避免重复比对同一对元素：

int matrix[n][n];
/* matrix已完成数据填充 */
int hasDuplicate = 0;
// 遍历每个元素的坐标(i1,j1)
for (int i1 = 0; i1 < n; i1++) {
    for (int j1 = 0; j1 < n; j1++) {
        int current = matrix[i1][j1];
        // 从(i1,j1)的下一个元素开始比对，避免重复比较
        for (int i2 = i1; i2 < n; i2++) {
            // 同一行时从j1+1开始遍历，不同行从列首开始遍历
            int startJ = (i2 == i1) ? (j1 + 1) : 0;
            for (int j2 = startJ; j2 < n; j2++) {
                if (current == matrix[i2][j2]) {
                    hasDuplicate = 1;
                    // 发现重复直接跳出所有循环
                    goto endCheck;
                }
            }
        }
    }
}
endCheck:
// 最终hasDuplicate为1表示存在重复数值，为0表示所有数值唯一

方案2：计数/哈希表校验（适用于所有场景，时间复杂度O(n²)，空间复杂度取决于数值范围） #

遍历所有元素的过程中记录已经出现过的数值，遇到已记录的数值直接判定重复，性能远高于暴力方案：
如果矩阵元素的数值范围可控（比如所有元素都是0~1000的整数），可以直接用数组计数：

int matrix[n][n];
/* matrix已完成数据填充 */
int hasDuplicate = 0;
// 假设元素最大值不超过MAX_VALUE，可按需调整数组大小
#define MAX_VALUE 1000
int seen[MAX_VALUE + 1] = {0};

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        int val = matrix[i][j];
        if (seen[val]) {
            hasDuplicate = 1;
            goto endCheck;
        }
        seen[val] = 1;
    }
}
endCheck:

如果数值范围不确定，可替换为哈希表实现，逻辑与上述代码一致，仅将计数数组替换为哈希表存储已出现的数值即可。

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