N阶矩阵相邻相同数字检测函数的正确性验证及优化咨询

方案正确性验证 #

你的现有代码逻辑完全正确：

• 逐行遍历阶段，每个元素仅和右侧相邻元素比较，j遍历到n-2为止，完全规避了行末越界问题，所有水平相邻元素对都被覆盖
• 逐列遍历阶段，每个元素仅和下方相邻元素比较，i遍历到n-2为止，规避了列末越界问题，所有垂直相邻元素对都被覆盖
• 找到匹配对后立即返回的逻辑也能减少不必要的遍历，没有逻辑漏洞。

效率优化说明 #

该问题的理论时间复杂度下界就是O(n²)：最坏情况（矩阵中完全没有相邻相等元素）下，你必须检查完所有相邻对才能得出结论，没有办法做到更低的时间复杂度，你的代码已经达到了最优时间复杂度。

如果要做工程层面的微优化，可以将两次循环合并为一次，减少循环变量初始化、判断的开销，同时提前缓存结构体成员避免重复解引用，优化后的参考代码如下：

int check (game_t *p){
    int n = p->n;
    int **board = p->board;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            // 检查右侧相邻元素
            if(j < n-1 && board[i][j] == board[i][j+1]) return 1;
            // 检查下方相邻元素
            if(i < n-1 && board[i][j] == board[i+1][j]) return 1;
        }
    }
    return 0;
}

这个优化在矩阵尺寸n较小的场景下感知不明显，当n很大时会有轻微的性能收益，而且保持了行优先的遍历顺序，对CPU缓存非常友好，缓存命中率和你原有的实现一致。

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