2025-07-22：跳过交替单元格的之字形遍历。用go语言，你有一个大小为 m 行 n 列的二维正整数数组 grid，要求以一种“锯齿形”的方式遍历整个数组：

1. 从左上角元素（第0行第0列）开始；

2. 在当前行从左向右依次访问元素，直到到达该行末尾；

3. 然后移动到下一行，从右向左访问该行元素，直到到达该行起始；

4. 按照这种左右交替的方式，依次遍历所有行。
   另外，需要在访问过程中跳过每个交替的单元格（即隔一个元素访问一次，只访问“跳过一个”后的元素）。

最终返回一个数组，包含按照上述规则访问的所有元素的值，顺序和跳过规则都要遵循以上描述。

2 <= n == grid.length <= 50。

2 <= m == grid[i].length <= 50。

1 <= grid[i][j] <= 2500。

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

输出： [1,4]。

解释：

题目来自力扣3417。

分步骤描述过程

1. 初始化：

   • 从第0行开始遍历，即 grid[0]。
   • 初始方向为从左到右（因为第0行是偶数行，索引从0开始）。

2. 第0行（从左到右）：

   • 行索引 i = 0，是偶数，因此从左到右遍历。
   • 跳过交替单元格的规则：从第0列开始，每次跳过下一个单元格，即访问第0列，跳过第1列，然后检查是否还有后续列。
     • 第0列：grid[0][0] = 1，访问 1。
     • 跳过第1列（不访问 2）。
   • 第0行遍历结束，访问到的元素：[1]。

3. 第1行（从右到左）：

   • 行索引 i = 1，是奇数，因此从右到左遍历。
   • 跳过交替单元格的规则：从最后一列开始，每次跳过下一个单元格，即访问第1列，跳过第0列，然后检查是否还有后续列。
     • 最后一列是第1列：grid[1][1] = 4，访问 4。
     • 跳过第0列（不访问 3）。
   • 第1行遍历结束，访问到的元素：[4]。

4. 合并结果：

   • 第0行访问到的元素：[1]。
   • 第1行访问到的元素：[4]。
   • 最终结果：[1, 4]。

时间复杂度分析

• 遍历每一行：m 行。
• 对于每一行，遍历的列数是 n，但跳过交替单元格后实际访问的列数约为 n/2。
• 因此，总的时间复杂度为 O(m * n/2) = O(m * n)。

额外空间复杂度分析

• 需要存储结果数组，最坏情况下（不跳过任何元素）大小为 m * n，但实际跳过后约为 m * n/2。
• 因此，额外空间复杂度为 O(m * n)（输出空间不计入额外空间时则为 O(1)，但通常输出空间也算额外空间）。

总结

• 时间复杂度：O(m * n)。
• 额外空间复杂度：O(m * n)（如果输出空间计入额外空间）。如果不计入输出空间，则为 O(1)。

Go完整代码如下：

package main

import (
	"fmt"
)

func zigzagTraversal(grid [][]int) (ans []int) {
	n := len(grid[0])
	end := n - 1 - n%2
	for i, row := range grid {
		if i%2 > 0 {
			for j := end; j >= 0; j -= 2 {
				ans = append(ans, row[j])
			}
		} else {
			for j := 0; j < n; j += 2 {
				ans = append(ans, row[j])
			}
		}
	}
	return
}

func main() {
	grid := [][]int{{1, 2}, {3, 4}}
	result := zigzagTraversal(grid)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def zigzag_traversal(grid):
    ans = []
    n = len(grid[0])
    end = n - 1 - n % 2
    for i, row in enumerate(grid):
        if i % 2 > 0:
            for j in range(end, -1, -2):
                ans.append(row[j])
        else:
            for j in range(0, n, 2):
                ans.append(row[j])
    return ans

if __name__ == "__main__":
    grid = [[1, 2], [3, 4]]
    result = zigzag_traversal(grid)
    print(result)