開發與維運

数组算法进阶之探究转置之法 | 带你学《Java面向对象编程》之十九

上一篇:数组排序-触摸算法的门槛 | 带你学《Java面向对象编程》之十八
【本节目标】
通过阅读本节内容,你将通过一则数组转置对算法这一范畴有更深的理解,并学会通过分析设计优化思路、改良算法,以更容易应对复杂的逻辑场景。

数组操作案例:数组反转

数组的反转操作指的是进行前后转置处理,即:首尾交换,例如,现在有一个数组,其内容如下:

  • 数组内容:1、2、3、4、5、6、7、8、9;
  • 交换后的内容:9、8、7、6、5、4、3、2、1;

对于数组的前后交换有两种做法:
做法一:定义一个新的数组而后按照逆序的方式保存(会产生无用的垃圾空间)

image.png
图一 数组转换结果图

class ArrayUtil {   
    public static void printArray(int temp []) {
        for (int x = 0 ; x < temp.lenght ; x ++) {
            System.out.print (temp[x] + “、”) ;
        }
        System.out.println() ;
    }
}
public class ArrayDemo {
     public static void main (String args[ ]) {
         int data [] = new int [] {1,2,3,4,5,6,7,8,9} ;
         int temp [] = new int [data.length] ;   //第二个数组
         int foot = temp.length – 1 ;   //第二个数组的脚标
         for (int x = 0 ; x < data.lenght ; x ++) {
             temp[foot --] = data [x] ;
         }
         data = temp ;
         ArrayUtil.printArray(data) ;
     }    
}

image.png
图二 转换结果

下面进行一下内存的分析处理,观察一下程序存在的问题。(以3个数据为例)

image.png
图三 数组转换内存分析图

做法二:在一个数组上进行转置(部分数据为例)

image.png
图四 数组转置分析

现在如果想实现这种转置最需要确定的是数组转换的次数,次数的计算:“数组长度÷2”,实际上并不需要去考虑数组是奇数个数还是偶数个数。

class ArrayUtil {
    public static void printArray(int temp []) {
         for (int x = 0 ; x < temp.lenght ; x ++) {
             System.out.print (temp[x] + “、”) ;
         }
         System.out.println() ;
     }
}
public class ArrayDemo {
     public static void main (String args[ ]) {
         int data [] = new int [] {1,2,3,4,5,6,7,8,9} ;
         int center = data.length /2 ;    //确定转换的次数
         int head = 0 ;   //操作的脚标
         int tail = data.length – 1 ;  //操作脚标
         for (int x = 0 ;x < center ;x ++) {
             int temp =data [head] ;
             data [head] = data [tail] ;
             data [tail] = temp ;
             head ++ ;
             tail -- ;
         }
         ArrayUtil.printArray(data) ;
     }    
}

image.png
图五 执行结果图

两种实现如果要进行比较可以发现,第一种处理方式循环次数较多,并且还会产生垃圾。而第二种实现,循环次数降低,但是存在有if判断增加了时间复杂度,可是可以减少无用对象的产生,以提升性能。
范例:将转换功能变为类定义

class ArrayUtil {
     public static void reverse(int data[]) {
         int center = data.length /2 ;    //确定转换的次数
         int head = 0 ;   //操作的脚标
         int tail = data.length – 1 ;  //操作脚标
         for (int x = 0 ;x < center ;x ++) {
             int temp =data [head] ;
             data [head] = data [tail] ;
             data [tail] = temp ;
             head ++ ;
             tail -- ;
          }
      }
      public static void printArray(int temp []) {
          for (int x = 0 ; x < temp.lenght ; x ++) {
              System.out.print (temp[x] + “、”) ;
          }
          System.out.println() ;
       }
}
public class ArrayDemo {
     public static void main (String args[ ]) {
         int data [] = new int [] {1,2,3,4,5,6,7,8,9} ;
         ArrayUtil.reverse(data) ;      //转置处理
         ArrayUtil.printArray(data) ;
     }    
}

image.png
图六 执行结果二

可以发现数组由于可以通过脚标进行元素的控制,所以相应的循环逻辑使用的会比较多。
想学习更多的Java的课程吗?从小白到大神,从入门到精通,更多精彩不容错过!免费为您提供更多的学习资源。
本内容视频来源于阿里云大学

下一篇:欲善其事,先利其器-数组类库 | 带你学《Java面向对象编程》之二十
更多Java面向对象编程文章查看此处

Leave a Reply

Your email address will not be published. Required fields are marked *