时间复杂度：检查矩阵中至少一行或一列的所有元素是否相等

Question

我的函数应该 return true 或 false 取决于方阵中是否存在至少一行或一列，其元素都彼此相等。

我已经解决了这个问题，但我相信时间复杂度是 O(n^2)，因为我使用嵌套循环解决了它。我想将我的解决方案更进一步，并尝试做得更好。如果有任何提示或提示，我将不胜感激！

def any_same_lines?(arr)
    # return true if any row's elements are all the same
    return true if arr.any? {|row| row.all? { |ele| ele == row[0] } }

    # return true if any column's elements are all the same
    k = 0
    while k < arr.length
        return true if arr.all? { |row| row[k] == arr[0][k] }
        k += 1
    end
    false
end

Answer 1

考虑到您的算法，您要查看每个单元格两次

在第一个循环中一次（每行）
在第二个循环中一次（对于每一列）

所以你的复杂度是 O(2N)，也就是 ~ O(N)。

所以在最坏的情况下，你真的不会做得比这更好。此外，如果出现差异（.all? 和 .any?），您也已经提前进行了救助，因此您的实际表现将取决于数据，但应该相当不错。

我希望还有进一步的优化空间（比如访问每个节点一次而不是两次），但不是从大角度来看。

时间复杂度：检查矩阵中至少一行或一列的所有元素是否相等

time complexity: check that all elements of at least one row or column in a matrix are equal

ruby

matrix

time-complexity