python - 检查矩阵中行/列中的5的更好算法

有没有一种好的算法来检查行或列中是否有5个相同的元素或对角线给定的方阵为6x6？

当然，有一种天真的算法:遍历每个点，然后针对矩阵中的每个点，遍历该行，col，然后遍历对角线。我想知道是否有更好的方法。

最佳答案

您可以检查单遍的整数矩阵中是否存在k个相同的元素。

假设n是矩阵的大小，m是最大的元素。我们有n列，n行和1个对角线。
对于每个列，行或对角线，我们最多具有n个不同的元素。

现在我们可以创建一个包含(n + n + 1)*(2 * m + 1)元素的直方图。代表
行，列和对角线每个都包含最多n个不同的元素。

size = (n + n + 1) * (2 * m + 1)
histogram = zeros(size, Int)

现在最棘手的部分是如何更新此直方图？

考虑一下伪代码中的此函数:

updateHistogram(i, j, element)

    if (element < 0)
        element = m - element;

    rowIndex        = i * m + element
    columnIndex     = n * m + j * m + element
    diagonalIndex   = 2 * n * m + element

    histogram[rowIndex] = histogram[rowIndex] + 1
    histogram[columnIndex] = histogram[columnIndex] + 1

    if (i = j)
        histogram[diagonalIndex] = histogram[diagonalIndex] + 1

现在您要做的就是迭代抛出直方图，并检查是否有一个元素> k

关于python - 检查矩阵中行/列中的5的更好算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8091248/