二维数组输出-面试算法题
实现数组的特殊输出方式
数组是我们最熟悉的顺序结构,遍历数组也有很多方法,但是像这样的二维数组我们应该怎么遍历呢?
我们仔细观察会发现规律,横纵坐标之和是由规律且有范围的,这就是我们的切入点。
先试着写代码,以下是第一次写的代码
public static void bialian(int a[][]) {
int num=0;int num2=0;
int max1=0, max2=1 ,max3=2,max4=3,max5=4,max6=5,max7=6,max8=7,max9=8,max10=59,max11=10;
for(int i=0;i<a.length;i++) {
for(int j=0;j<a[0].length;j++)
{
num++;
if((i+j)==max1){
num2++;
System.out.print(a[i][j]+" ");
}
}
}
for(int i=0;i<a.length;i++) {
for(int j=0;j<a[0].length;j++)
{
num++;
if((i+j)==max2){
num2++;
System.out.print(a[i][j]+" ");
}
}
}
for(int i=0;i<a.length;i++) {
for(int j=0;j<a[0].length;j++)
{
num++;
if((i+j)==max3){
num2++;
System.out.print(a[i][j]+" ");
}
}
}
for(int i=0;i<a.length;i++) {
for(int j=0;j<a[0].length;j++)
{
num++;
if((i+j)==max4){
num2++;
System.out.print(a[i][j]+" ");
}
}
}
for(int i=0;i<a.length;i++) {
for(int j=0;j<a[0].length;j++)
{
num++;
if((i+j)==max5){
num2++;
System.out.print(a[i][j]+" ");
}
}
}
for(int i=0;i<a.length;i++) {
for(int j=0;j<a[0].length;j++)
{
num++;
if((i+j)==max6){
num2++;
System.out.print(a[i][j]+" ");
}
}
}
for(int i=0;i<a.length;i++) {
for(int j=0;j<a[0].length;j++)
{
num++;
if((i+j)==max7){
num2++;
System.out.print(a[i][j]+" ");
}
}
}
for(int i=0;i<a.length;i++) {
for(int j=0;j<a[0].length;j++)
{
num++;
if((i+j)==max8){
num2++;
System.out.print(a[i][j]+" ");
}
}
}
for(int i=0;i<a.length;i++) {
for(int j=0;j<a[0].length;j++)
{
num++;
if((i+j)==max9){
num2++;
System.out.print(a[i][j]+" ");
}
}
}
for(int i=0;i<a.length;i++) {
for(int j=0;j<a[0].length;j++)
{
num++;
if((i+j)==max10){
num2++;
System.out.print(a[i][j]+" ");
}
}
}
for(int i=0;i<a.length;i++) {
for(int j=0;j<a[0].length;j++)
{
num++;
if((i+j)==max11){
num2++;
System.out.print(a[i][j]+" ");
}
}
}
System.out.println("");
System.out.println(num+" "+num2);
System.out.println(a.length+" "+a[0].length);
}
没错,重复代码太多。多次调用循环,复杂度太高。但是起码是实现了,不过这种算法确实是没什么实用价值
下面是优化的代码
public static void bianli2(int a[][]) {
int num=0;
int m=a.length; //m代表行数
int n=a[0].length; //n代表列数
int size=m+n-2;
for(int i=0;i<=size;i++) {
for(int x=0;x<=i&&x<m&&(i-x)<n;x++) {
System.out.print(a[x][i-x]+"\t");
num++;
}
for(int y=n-1;y>=0&&(i-y)>0&&(i-y)<m;y--)
{
System.out.print(a[i-y][y]+"\t");
num++;
}
System.out.println("");
}
System.out.println("时间复杂度为:"+num);
}
是不是惊呆了,少写了很多很多代码。复杂度也大大降低。下面还是来分析一下代码。
我们还是抓住坐标特点,根据坐标的和来输出。对于一个二维数组来说,我们先x轴来当作标准来输出,同时注意控制x和y的范围。
important:
x<=m&&x<=i(也就是x+y)&&(i-x)<n
这样一会发现还有一部分没有输出完,然后再通过y进行控制,同时通过控制(x+y)使之前的不会再次输出。然后下面的输出完就大功告成了。
总结:
- 应该多画画图 这样有助于组织逻辑
- 应该多用一些逻辑判断,减少不必要的循环
- 一边敲代码一边思考,不要不敢写代码。