对角线遍历矩阵

拼多多技术岗 7月3号笔试 第一题

题目内容

给你一个大小为 $m$ × $n$ 的矩阵 $mat$，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素，对角线遍历的顺序如图所示。

输入描述

第一行包含两个整数 $m$ 和 $n$，表示矩阵的行数和列数（$1\le m,n\le 100$）。
接下来的 $m$ 行，每行包含 $n$ 个整数，表示矩阵的元素（整数范围在 $[-10000,10000]$ 之间）。

输出描述

输出一行，包含按对角线遍历顺序排列的矩阵元素，元素之间用空格隔开。

样例1

输入

3 3
1 2 3
4 5 6
7 8 9

输出

7 4 8 9 5 1 2 6 3

题解和思路

思路

实现思路：模拟

1. 按照题目给出的示例进行模拟即可，主要考虑边界情况。
2. 当走反对角时,走到j==0时移动规律
   1. 当i==0时需要将j--
   2. 当i != 0需要将i--
3. 当走对角，走到j==m-1时移动规律
   1. 当i == n -1, 需要将j++
   2. 当j == m -1， 需要将i--
4. 总体时间复杂度为O（n * m）

C++

#include<bits/stdc++.h>
using namespace std;



int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i <  n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    vector<int> ans(n * m);
    int index = 0;
    // 0 反对角 1对角
    int flag = 0;
    int i = n - 1, j = 0;
    while (index < n * m) {
        ans[index++] = grid[i][j];
        if (flag == 0) {
            if (i == 0) {
                j++;
                flag = 1;
            } else if (j == 0) {
               i--;
               flag = 1;
            } else {
               i--;
               j--;
            }
        } else {
            if (i == n -1) {
                j++;
                flag = 0;
            } else if (j == m - 1) {
                i--;
                flag = 0;
            } else {
                i++;
                j++;
            }
        }
        
    }
    //输出结果
    for (int i = 0; i < n * m; i++) {
        if (i > 0) {
            cout << " ";
        }
        cout << ans[i];
    }
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String line;
        while ((line = br.readLine()) != null) {
            sb.append(line).append(" ");
        }

        String[] input = sb.toString().trim().split("\\s+");
        int idx = 0;

        int n = Integer.parseInt(input[idx++]);
        int m = Integer.parseInt(input[idx++]);

        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = Integer.parseInt(input[idx++]);
            }
        }

        int[] ans = new int[n * m];
        int index = 0;

        // 0 反对角 1对角
        int flag = 0;
        int i = n - 1, j = 0;

        while (index < n * m) {
            ans[index++] = grid[i][j];

            if (flag == 0) {
                if (i == 0) {
                    j++;
                    flag = 1;
                } else if (j == 0) {
                    i--;
                    flag = 1;
                } else {
                    i--;
                    j--;
                }
            } else {
                if (i == n - 1) {
                    j++;
                    flag = 0;
                } else if (j == m - 1) {
                    i--;
                    flag = 0;
                } else {
                    i++;
                    j++;
                }
            }
        }

        // 输出结果
        StringBuilder out = new StringBuilder();
        for (int k = 0; k < n * m; k++) {
            if (k > 0) {
                out.append(" ");
            }
            out.append(ans[k]);
        }
        System.out.print(out.toString());
    }
}

python

import sys

data = list(map(int, sys.stdin.read().split()))
idx = 0

n = data[idx]
idx += 1
m = data[idx]
idx += 1

grid = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        grid[i][j] = data[idx]
        idx += 1

ans = [0] * (n * m)
index = 0

# 0 反对角 1对角
flag = 0
i = n - 1
j = 0

while index < n * m:
    ans[index] = grid[i][j]
    index += 1

    if flag == 0:
        if i == 0:
            j += 1
            flag = 1
        elif j == 0:
            i -= 1
            flag = 1
        else:
            i -= 1
            j -= 1
    else:
        if i == n - 1:
            j += 1
            flag = 0
        elif j == m - 1:
            i -= 1
            flag = 0
        else:
            i += 1
            j += 1

# 输出结果
print(*ans)

Javascript

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const input = [];

rl.on("line", (line) => {
    input.push(...line.trim().split(/\s+/));
});

rl.on("close", () => {
    let idx = 0;

    const n = Number(input[idx++]);
    const m = Number(input[idx++]);

    const grid = Array.from({ length: n }, () => Array(m));

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            grid[i][j] = Number(input[idx++]);
        }
    }

    const ans = new Array(n * m);
    let index = 0;

    // 0 反对角 1对角
    let flag = 0;
    let i = n - 1, j = 0;

    while (index < n * m) {
        ans[index++] = grid[i][j];

        if (flag === 0) {
            if (i === 0) {
                j++;
                flag = 1;
            } else if (j === 0) {
                i--;
                flag = 1;
            } else {
                i--;
                j--;
            }
        } else {
            if (i === n - 1) {
                j++;
                flag = 0;
            } else if (j === m - 1) {
                i--;
                flag = 0;
            } else {
                i++;
                j++;
            }
        }
    }

    // 输出结果
    console.log(ans.join(" "));
});

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)

	var n, m int
	fmt.Fscan(in, &n, &m)

	grid := make([][]int, n)
	for i := 0; i < n; i++ {
		grid[i] = make([]int, m)
		for j := 0; j < m; j++ {
			fmt.Fscan(in, &grid[i][j])
		}
	}

	ans := make([]int, n*m)
	index := 0

	// 0 反对角 1对角
	flag := 0
	i, j := n-1, 0

	for index < n*m {
		ans[index] = grid[i][j]
		index++

		if flag == 0 {
			if i == 0 {
				j++
				flag = 1
			} else if j == 0 {
				i--
				flag = 1
			} else {
				i--
				j--
			}
		} else {
			if i == n-1 {
				j++
				flag = 0
			} else if j == m-1 {
				i--
				flag = 0
			} else {
				i++
				j++
			}
		}
	}

	// 输出结果
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for k := 0; k < n*m; k++ {
		if k > 0 {
			fmt.Fprint(out, " ")
		}
		fmt.Fprint(out, ans[k])
	}
}