Easy

题目描述

给你一个 m x n 的二维正整数数组 grid。

你的任务是以之字形模式遍历 grid，同时跳过每个交替的单元格。

之字形模式遍历定义为执行以下操作：

  • 从左上角单元格 (0, 0) 开始。
  • 在一行内向右移动，直到到达行的末尾。
  • 向下移动到下一行，然后向左遍历直到到达行的开头。
  • 继续在向右和向左遍历之间交替，直到遍历完每一行。

注意，在遍历过程中必须跳过每个交替的单元格。

返回一个整数数组 result，按顺序包含在跳跃的之字形遍历过程中访问的单元格的值。

示例 1：

输入：grid = [[1,2],[3,4]]
输出：[1,4]

示例 2：

输入：grid = [[2,1],[2,1],[2,1]]
输出：[2,1,2]

示例 3：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,3,5,7,9]

提示：

  • 2 <= n == grid.length <= 50
  • 2 <= m == grid[i].length <= 50
  • 1 <= grid[i][j] <= 2500

解题思路

解题思路

这道题要求我们按照之字形模式遍历二维数组，并跳过每个交替的单元格。

核心思路：

  1. 之字形遍历：偶数行从左到右，奇数行从右到左
  2. 跳跃规则：每隔一个单元格取一次值，即每次移动2步
  3. 实现方式：遍历每一行，根据行号奇偶性决定方向，每次步长为2

详细分析：

  • 对于偶数行（0, 2, 4…），从索引0开始，每次+2（即0, 2, 4…）
  • 对于奇数行（1, 3, 5…），需要从右侧开始跳跃遍历
  • 奇数行的起始位置需要特殊计算：如果列数为奇数，从最后一列开始；如果列数为偶数，从倒数第二列开始
  • 这样可以保证跳跃的连续性和正确性

算法步骤：

  1. 遍历每一行
  2. 根据行号判断遍历方向
  3. 按照步长2进行跳跃式访问
  4. 将访问到的值加入结果数组

时间复杂度为O(m×n)，空间复杂度为O(1)（不考虑结果数组）。

代码实现

class Solution {
public:
    vector<int> zigzagTraversal(vector<vector<int>>& grid) {
        vector<int> result;
        int m = grid.size(), n = grid[0].size();
        
        for (int i = 0; i < m; i++) {
            if (i % 2 == 0) {
                // 偶数行：从左到右，跳跃遍历
                for (int j = 0; j < n; j += 2) {
                    result.push_back(grid[i][j]);
                }
            } else {
                // 奇数行：从右到左，跳跃遍历
                int start = (n % 2 == 1) ? n - 1 : n - 2;
                for (int j = start; j >= 0; j -= 2) {
                    result.push_back(grid[i][j]);
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def zigzagTraversal(self, grid: List[List[int]]) -> List[int]:
        result = []
        m, n = len(grid), len(grid[0])
        
        for i in range(m):
            if i % 2 == 0:
                # 偶数行：从左到右，跳跃遍历
                for j in range(0, n, 2):
                    result.append(grid[i][j])
            else:
                # 奇数行：从右到左，跳跃遍历
                start = n - 1 if n % 2 == 1 else n - 2
                for j in range(start, -1, -2):
                    result.append(grid[i][j])
        
        return result

public class Solution {
    public IList<int> ZigzagTraversal(int[][] grid) {
        var result = new List<int>();
        int m = grid.Length, n = grid[0].Length;
        
        for (int i = 0; i < m; i++) {
            if (i % 2 == 0) {
                // 偶数行：从左到右，跳跃遍历
                for (int j = 0; j < n; j += 2) {
                    result.Add(grid[i][j]);
                }
            } else {
                // 奇数行：从右到左，跳跃遍历
                int start = (n % 2 == 1) ? n - 1 : n - 2;
                for (int j = start; j >= 0; j -= 2) {
                    result.Add(grid[i][j]);
                }
            }
        }
        
        return result;
    }
}

/**
 * @param {number[][]} grid
 * @return {number[]}
 */
var zigzagTraversal = function(grid) {
    const result = [];
    let skip = false;
    
    for (let i = 0; i < grid.length; i++) {
        if (i % 2 === 0) {
            // Left to right
            for (let j = 0; j < grid[i].length; j++) {
                if (!skip) {
                    result.push(grid[i][j]);
                }
                skip = !skip;
            }
        } else {
            // Right to left
            for (let j = grid[i].length - 1; j >= 0; j--) {
                if (!skip) {
                    result.push(grid[i][j]);
                }
                skip = !skip;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)需要遍历整个网格，每个元素最多访问一次
空间复杂度O(1)除了结果数组外，只使用了常数额外空间

相关题目