邏輯矩陣....解決方案

Question

假設你有一個N×N矩陣，你必須檢查它是否是一個上對角矩陣。有沒有什麼通用的方法來解決這個問題？

我闡述我的問題： 有些事情是這樣的： 假設你有具有N的值NXN矩陣= 4 然後矩陣看起來就像這樣：

|5 6 9 2| 
|1 8 4 9| 
|5 8 1 6| 
|7 6 3 2| 

它是一個4X4的方陣如果再是上三角矩陣會是這個樣子：

|5 6 9 2| 
|1 8 4 0| 
|5 8 0 0| 
|7 0 0 0| 

我需要用任何語言來生成一個通用的程序，請檢查是否方陣是上trailgle與否。

Answer 1

只是爲了檢查，是（1,1）左下角和（n，n）在這些圖的右上角？ （這不是矩陣通常寫的方式！）。

在任何情況下，該算法是O(N^2)不管是什麼，我想 - 你必須做一些與所有n*(n-1)/2可能的非零項與row>column。你只需要通過它們，看看它們是否爲零 - 當然，你應該以最有效的方式通過矩陣工作，這取決於它是存儲列還是行。

此外，你的矩陣是否真的充滿整數，或者你需要檢查是否爲零？

基本上你需要檢查

for col = 2, n 
    for row = col+1, n 
     if matrix(row, col) != 0 
     return false 
     endif 
    endfor 
endfor 

雖然極端情況檢查從@paxdiablo是一個好主意。

Answer 2

如果你想要一個簡單的解決方案（使用基於1的索引）：

def isUpperDiag(matrix[][]): 
    if matrix.height != matrix.width: 
     return false      # must be square 
    if matrix.height == 1: 
     return true      # not sure how to treat 1x1 
    for row = 2 to matrix.height: 
     for col = matrix.width - row + 2 to matrix.width: 
      if matrix[row][col] != 0: 
       return false 
    return true 

這是假設零被允許在左上角。如果沒有，你也必須檢查。

合理簡單。在你的4x4矩陣上，它迭代從2到4的行。對於第2行，它迭代從4到4的列。對於第3行，它迭代從3到4的列。對於第4行，它迭代從2到4的列。

在這些單元的每一箇中，它只是檢查數字是否爲零。如果不是，則不是左上角三角形。如果所有單元檢查爲零，那麼它是。

Answer 3

假設在你的情況下這是可行的，你可以選擇一個經典的空間交易時間策略。 （我假設你使用的是OO語言 - 這個想法對於非OO語言也適用，但是需要更多的努力來確保同一矩陣的不同表示保持同步）。

而不是將矩陣表示爲數組（或與表示一起）將它保持爲一組非零值？

那麼，你是代表爲：

|5 6 9 2| 
|1 8 4 0| 
|5 8 0 0| 
|7 0 0 0| 

將成爲（或存儲爲）

1,1=5 
1,2=6 
1,3=9 
... 
4,1=7 

，如果這是可行的，你也可以在兩（上下分割該套對角線）

在第一基質的情況下

這樣：

|5 6 9 2| 
|1 8 4 9| 
|5 8 1 6| 
|7 6 3 2| 

是：

UpperMap - 

1,1=5 
1,2=6 
1,3=9 
... 
4,1=7 

Lower Map- 

2,4=9 
3,3=1 
... 
4,4=2 

在這種情況下，你的測試將是「詢問是否較低的HashMap是空的」。如上所述，如果您需要在矩陣上執行更多的「傳統」操作，您可以將它與2位地圖一起存儲爲數組，並且在矩陣不是不可變的情況下，您將不得不提供方法改變「細胞」值。

另一個折衷（除了空間）是創建一個新的矩陣需要更多的CPU時間。但如果你不經常創建和修改這些東西，而且經常需要測試較低的對角線，這可能是值得的。

一個更極端的方法：

對於每個矩陣建立一個位圖表示的（非零細胞是1，零細胞得到一個0），並使用邏輯操作以檢查部的「空」。