拼多多笔试真题-对角线遍历矩阵(C++/Py/Java /Js/Go)
对角线遍历矩阵
拼多多技术岗 7月3号笔试 第一题
题目内容
给你一个大小为mmm×nnn的矩阵matmatmat，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素，对角线遍历的顺序如图所示。
输入描述
第一行包含两个整数mmm和nnn，表示矩阵的行数和列数（1≤m,n≤1001 \le m,n \le 1001≤m,n≤100）。
接下来的mmm行，每行包含nnn个整数，表示矩阵的元素（整数范围在[−10000,10000][-10000, 10000][−10000,10000]之间）。
输出描述
输出一行，包含按对角线遍历顺序排列的矩阵元素，元素之间用空格隔开。
样例1
输入
3 3 1 2 3 4 5 6 7 8 9输出
7 4 8 9 5 1 2 6 3题解和思路
思路
实现思路：模拟
- 按照题目给出的示例进行模拟即可，主要考虑边界情况。
- 当走反对角时,走到
j==0时移动规律- 当
i==0时需要将j-- - 当
i != 0需要将i--
- 当
- 当走对角，走到
j==m-1时移动规律- 当
i == n -1, 需要将j++ - 当
j == m -1， 需要将i--
- 当
- 总体时间复杂度为
O（n * m）
C++
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m));for(inti=0;i<n;i++){for(intj=0;j<m;j++){cin>>grid[i][j];}}vector<int>ans(n*m);intindex=0;// 0 反对角 1对角intflag=0;inti=n-1,j=0;while(index<n*m){ans[index++]=grid[i][j];if(flag==0){if(i==0){j++;flag=1;}elseif(j==0){i--;flag=1;}else{i--;j--;}}else{if(i==n-1){j++;flag=0;}elseif(j==m-1){i--;flag=0;}else{i++;j++;}}}//输出结果for(inti=0;i<n*m;i++){if(i>0){cout<<" ";}cout<<ans[i];}return0;}Java
importjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));StringBuildersb=newStringBuilder();Stringline;while((line=br.readLine())!=null){sb.append(line).append(" ");}String[]input=sb.toString().trim().split("\\s+");intidx=0;intn=Integer.parseInt(input[idx++]);intm=Integer.parseInt(input[idx++]);int[][]grid=newint[n][m];for(inti=0;i<n;i++){for(intj=0;j<m;j++){grid[i][j]=Integer.parseInt(input[idx++]);}}int[]ans=newint[n*m];intindex=0;// 0 反对角 1对角intflag=0;inti=n-1,j=0;while(index<n*m){ans[index++]=grid[i][j];if(flag==0){if(i==0){j++;flag=1;}elseif(j==0){i--;flag=1;}else{i--;j--;}}else{if(i==n-1){j++;flag=0;}elseif(j==m-1){i--;flag=0;}else{i++;j++;}}}// 输出结果StringBuilderout=newStringBuilder();for(intk=0;k<n*m;k++){if(k>0){out.append(" ");}out.append(ans[k]);}System.out.print(out.toString());}}python
importsys data=list(map(int,sys.stdin.read().split()))idx=0n=data[idx]idx+=1m=data[idx]idx+=1grid=[[0]*mfor_inrange(n)]foriinrange(n):forjinrange(m):grid[i][j]=data[idx]idx+=1ans=[0]*(n*m)index=0# 0 反对角 1对角flag=0i=n-1j=0whileindex<n*m:ans[index]=grid[i][j]index+=1ifflag==0:ifi==0:j+=1flag=1elifj==0:i-=1flag=1else:i-=1j-=1else:ifi==n-1:j+=1flag=0elifj==m-1:i-=1flag=0else:i+=1j+=1# 输出结果print(*ans)Javascript
constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});constinput=[];rl.on("line",(line)=>{input.push(...line.trim().split(/\s+/));});rl.on("close",()=>{letidx=0;constn=Number(input[idx++]);constm=Number(input[idx++]);constgrid=Array.from({length:n},()=>Array(m));for(leti=0;i<n;i++){for(letj=0;j<m;j++){grid[i][j]=Number(input[idx++]);}}constans=newArray(n*m);letindex=0;// 0 反对角 1对角letflag=0;leti=n-1,j=0;while(index<n*m){ans[index++]=grid[i][j];if(flag===0){if(i===0){j++;flag=1;}elseif(j===0){i--;flag=1;}else{i--;j--;}}else{if(i===n-1){j++;flag=0;}elseif(j===m-1){i--;flag=0;}else{i++;j++;}}}// 输出结果console.log(ans.join(" "));});Go
packagemainimport("bufio""fmt""os")funcmain(){in:=bufio.NewReader(os.Stdin)varn,mintfmt.Fscan(in,&n,&m)grid:=make([][]int,n)fori:=0;i<n;i++{grid[i]=make([]int,m)forj:=0;j<m;j++{fmt.Fscan(in,&grid[i][j])}}ans:=make([]int,n*m)index:=0// 0 反对角 1对角flag:=0i,j:=n-1,0forindex<n*m{ans[index]=grid[i][j]index++ifflag==0{ifi==0{j++flag=1}elseifj==0{i--flag=1}else{i--j--}}else{ifi==n-1{j++flag=0}elseifj==m-1{i--flag=0}else{i++j++}}}// 输出结果out:=bufio.NewWriter(os.Stdout)deferout.Flush()fork:=0;k<n*m;k++{ifk>0{fmt.Fprint(out," ")}fmt.Fprint(out,ans[k])}}