判断方阵是否存在全相等行或列的算法时间复杂度优化咨询

首先明确前提：该问题的最坏时间复杂度理论下界为O(n²)，不存在更低时间复杂度的实现方案。原因是如果待校验的方阵完全不存在整行/整列元素相等的情况，你必须遍历所有n²个元素完成校验才能返回false，因此我们能优化的只有平均场景执行耗时与常数项开销。

具体可落地的优化点 #

• 边界情况提前返回
  针对n≤1的极小方阵可以直接返回true，跳过后续所有校验逻辑，减少不必要的运算。
• 减少重复索引查找开销
  现有代码多次读取arr.length、arr[0][k]这类索引值，可以提前缓存重复读取的变量，降低常数项开销。
• 调整校验顺序适配业务场景
  现有代码先校验行再校验列，如果你的业务场景中整列相等的出现概率更高，可以调换校验顺序，更早触发提前返回，降低平均耗时。
• 列校验写法优化（Ruby风格适配+性能优化二合一）
  原有的while循环可以替换为Ruby内置的迭代器，可读性更高的同时也能利用Ruby内部优化的C实现迭代逻辑，性能优于纯Ruby层面的while循环。

优化后代码示例 #

def any_same_lines?(arr)
  n = arr.size
  # 边界情况提前返回
  return true if n <= 1

  # 行校验逻辑保持，all?本身已实现提前终止
  return true if arr.any? { |row|
    row_first = row[0]
    row.all? { |ele| ele == row_first }
  }

  # 列校验优化：提前缓存首行，减少重复索引访问
  first_row = arr[0]
  return true if first_row.each_index.any? { |k|
    col_first = first_row[k]
    arr.all? { |row| row[k] == col_first }
  }

  false
end

额外可选优化（仅特定场景适用） #

如果你的运行环境是JRuby（无GIL限制），且方阵规模极大（n≥1000），可以考虑拆分行列校验任务到多线程并行执行，进一步降低耗时，纯CRuby环境下不推荐该方案，GIL会导致多线程反而增加调度开销。

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