LeetCode二維數組中如何實現對角線遍歷

LeetCode二維數組中如何實現對角線遍歷

在LeetCode等編程競賽和面試中，二維數組的對角線遍歷是一個常見的算法問題。這類問題不僅考察了我們對數組的理解，還要求我們能夠靈活運用循環和條件判斷來實現復雜的遍歷邏輯。本文將詳細介紹如何在二維數組中實現對角線遍歷，并通過代碼示例幫助讀者更好地理解這一過程。

問題描述

給定一個二維數組 matrix，要求按照對角線順序遍歷數組中的所有元素。例如，給定以下二維數組：

[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

按照對角線遍歷的順序，輸出應為：[1, 2, 4, 7, 5, 3, 6, 8, 9]。

解題思路

要實現對角線遍歷，我們需要明確以下幾點：

1. 對角線的方向：對角線遍歷通常有兩種方向，一種是從左上到右下，另一種是從右上到左下。我們需要交替使用這兩種方向。
2. 遍歷的起點：每條對角線的起點要么是第一行的某個元素，要么是最后一列的某個元素。
3. 邊界條件：在遍歷過程中，我們需要確保不會越界。

基于以上幾點，我們可以采用以下步驟來實現對角線遍歷：

1. 確定對角線的起點：從第一行的每個元素開始，向右下方遍歷；然后從最后一列的每個元素開始，向左下方遍歷。
2. 交替方向：每次遍歷完一條對角線后，切換遍歷方向。
3. 邊界檢查：在遍歷過程中，始終檢查當前元素是否在數組的邊界內。

代碼實現

以下是使用Python實現的代碼示例：

def diagonal_traverse(matrix):
    if not matrix:
        return []
    
    rows, cols = len(matrix), len(matrix[0])
    result = []
    direction = 1  # 1表示從下到上，-1表示從上到下
    row, col = 0, 0
    
    for _ in range(rows * cols):
        result.append(matrix[row][col])
        
        # 根據當前方向更新行和列
        if direction == 1:
            if col == cols - 1:
                row += 1
                direction = -1
            elif row == 0:
                col += 1
                direction = -1
            else:
                row -= 1
                col += 1
        else:
            if row == rows - 1:
                col += 1
                direction = 1
            elif col == 0:
                row += 1
                direction = 1
            else:
                row += 1
                col -= 1
    
    return result

# 測試用例
matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
print(diagonal_traverse(matrix))  # 輸出: [1, 2, 4, 7, 5, 3, 6, 8, 9]

代碼解析

1. 初始化：首先檢查輸入的二維數組是否為空。如果為空，直接返回空列表。
2. 變量定義：定義 rows 和 cols 分別表示數組的行數和列數。result 用于存儲遍歷結果。direction 用于控制遍歷方向，初始值為1，表示從下到上。
3. 遍歷過程：使用一個 for 循環遍歷數組中的所有元素。在每次循環中，將當前元素添加到 result 中，并根據當前方向更新行和列。
4. 方向切換：當遍歷到邊界時，切換遍歷方向，并更新行和列的值。

復雜度分析

• 時間復雜度：O(M * N)，其中 M 是數組的行數，N 是數組的列數。我們需要遍歷數組中的每個元素一次。
• 空間復雜度：O(1)，除了存儲結果的 result 列表外，我們只使用了常數級別的額外空間。

總結

通過本文的介紹，我們了解了如何在二維數組中實現對角線遍歷。這一問題的關鍵在于確定對角線的起點和方向，并在遍歷過程中正確處理邊界條件。通過合理的代碼實現，我們可以高效地完成這一任務。希望本文的內容能夠幫助讀者更好地理解和掌握這一算法技巧。