Java 中的托普利茨矩阵

托普利兹矩阵（Toeplitz matrix）是线性代数中的一种特殊类型的矩阵，其中从左到右的每条向下对角线包含相同的元素。它以数学家奥托·托普利兹（Otto Toeplitz）的名字命名。托普利兹矩阵是一个 n×n 的方阵，其中每个单元格 A[i][j] 的值都与 A[i-1][j-1]、A[i+1][j+1]、A[i-2][j-2]、A[i+2][j+2] 等相同，对于所有有效的单元格 A[i+k][j+k] 或 A[i-k][j-k]。简单来说，每条对角线上的元素都是常数。

示例

输入

输出

 
True   

输入

输出

 
True   

输入

输出

 
False   

方法：对角线比较

方法很简单，我们检查矩阵第一行和第一列（或最后一行和最后一列）的每个元素。我们跟踪每个元素的向下对角线，并验证其所有元素是否具有相同的值。如果遇到任何值不同的向下对角线，我们立即返回 false。

在实现方面，我们需要使用嵌套循环来遍历矩阵并检查向下对角线。如果所有对角线都有相同的值，则方法应返回 true；否则返回 false。

上述代码的实现

算法

步骤 1：创建一个方法 checkDiagonal(matrix, row, col)，用于检查矩阵中从位置 (row, col) 开始的向下对角线的所有元素是否相同。

步骤 2：创建一个方法 isToeplitz(matrix)，用于检查矩阵中从左到右的所有向下对角线是否具有相同的元素。

步骤 3：遍历第一行的每个元素，并使用 checkDiagonal(matrix, 0, i) 检查其向下对角线。

步骤 4：遍历第一列的每个元素，并使用 checkDiagonal(matrix, i, 0) 检查其向下对角线。

步骤 5：如果任何向下对角线包含不同的元素，则返回 false；否则，在两个循环结束后返回 true。

实施

文件名： ToeplitzMatrixChecker1.java

输出

 
The given matrix is a Toeplitz matrix.   

时间复杂度：时间复杂度

代码的时间复杂度为 O(N * M)，其中 N 是矩阵的行数，M 是矩阵的列数。这是因为代码从第一行和第一列开始遍历所有矩阵元素。它检查每个元素的向下对角线，直到到达右下角。

辅助空间：代码的辅助空间复杂度为 O(1)。

上述方法的改进

该算法涉及完整的矩阵遍历，其中每个元素都与其上面的对角线元素进行比较。如果任何元素与其对角线邻居不匹配，则认为该矩阵不是“托普利兹”矩阵，并且方法返回 false。但是，如果所有元素都满足条件，则方法返回 true，表示该矩阵是“托普利兹”矩阵。

文件名： ToeplitzMatrixChecker2.java

输出

 
The given matrix is a Toeplitz matrix.   

时间复杂度：提供的代码的时间复杂度为 O(N * M)，其中 N 是矩阵的行数，M 是矩阵的列数。这是因为代码遍历从 (1, 1) 到 (N-1, M-1) 的所有矩阵元素，并对每个元素执行常数时间的比较。

辅助空间：辅助空间复杂度为 O(1)，这意味着代码使用的额外空间量与输入矩阵的大小无关，保持恒定。

方法：基于哈希的方法

在 m×n 维的矩阵中，我们考虑索引为 (i, j) 的元素。为了使矩阵对角线恒定，它要求包含元素 (i, j) 的对角线上的所有元素都相同。我们可以根据索引识别此对角线上的其他元素，这些索引遵循 (i+k, j+k) 或 (i-k, j-k) 的模式。值得注意的是，无论这些索引的具体 (x, y) 值如何，它们的差值都保持恒定，等于 (i - j)。

为了进一步说明这一点，我们可以用图表来可视化。以黄色对角线为例。此对角线上任何索引的 x 值和 y 值之间的差值始终为 2（例如，2-0、3-1、4-2、5-3）。同样的观察结果可以扩展到矩阵中的所有其他主体对角线。

在托普利兹矩阵的上下文中，每条对角线都有一个唯一的差值。例如，红色对角线在其 x 值和 y 值之间有一个差值为 3，绿色对角线有一个差值为 0，橙色对角线有一个差值为 -2，依此类推。

利用此属性，我们可以利用常数对角线矩阵在每条对角线上应具有唯一元素这一事实。为了实现这一点，我们使用 HashMap 来存储键值对。键代表特定对角线的唯一索引差值，相应的值将是该对角线上找到的任何元素。

在此过程中，如果我们遇到一个元素的值与其在 HashMap 中对应的存储键值不匹配，我们可以立即得出该矩阵不是常数对角线矩阵的结论，并返回 false。否则，如果其各自对角线上的所有元素都保持此属性，则该矩阵确实是常数对角线矩阵，我们可以返回 true。

算法

步骤 1：创建一个哈希图来存储矩阵的元素。

步骤 2：遍历矩阵中的每个元素。

步骤 3：检查当前对角线键是否已存在于映射中。

步骤 4：如果当前对角线键存在于映射中，则将当前元素与相应元素进行比较。

步骤 5：如果元素不匹配，则该矩阵不是托普利兹矩阵。

步骤 6：如果对角线键在映射中不存在，则添加它以及当前元素。

步骤 7：如果所有元素都满足托普利兹属性，则该矩阵是托普利兹矩阵。

实施

文件名： ToeplitzMatrixChecker.java

输出

 
The given matrix is a Toeplitz matrix.   

时间复杂度：提供的代码的时间复杂度为 O(numRows * numCols)，其中 numRows 和 numCols 分别是输入矩阵的行数和列数。这是因为代码正好遍历所有矩阵元素一次，并且对于每个元素，它在 HashMap 中执行常数时间的查找或插入。

辅助空间：辅助空间复杂度也为 O(numRows * numCols)。这是因为用于存储 HashMap (diagonalMap) 的空间，在最坏的情况下最多可以有 numRows * numCols 个键值对。