小言_互联网的博客

阿里面试:我差点倒在了数组上

401人阅读  评论(0)

一、数组的概述

1.1 什么是数组?

数组(Array)是多个相同类型数据一定顺序排列的集合,并使用一个名字命名,并通过编号的方式对这些数据进行统一管理。

1.2 数组的相关概念

数组名
下标(或索引)
元素
数组的长度

1.3 数组的特点

(1)创建数组对象会在内存中开辟一整块连续的空间,而数组名中引用的是这块连续空间的首地址。
(2)数组本身是引用数据类型,而数组中的元素可以是任何数据类型,包括基本数据类型和引用数据类型。
(3)数组的长度一旦确定,就不能修改。
(4)数组是有序排列的,我们可以直接通过下标(或索引)的方式获取指定位置的元素,速度很快。

1.4 数组的分类

按照维度分:一维数组、二维数组、多维数组
按照元素的数据类型分:基本数据类型元素的数组、引用数据类型元素的数组(即对象数组)

二、一维数组的使用

2.1 数组的声明和初始化

2.1.1 静态初始化

静态初始化是指:数组的初始化和数组元素的赋值操作同时进行

int[] ids=new int[]{1001,1002,1003,1004};

2.1.2 动态初始化

动态初始化是指:数组的初始化和数组元素的赋值操作分开进行

String[] names=new String[4];
names[0]="张三";//数组的下标(索引)从0开始,到数组的长度-1结束
names[1]="李四";
names[2]="王五";
names[3]="赵六";

注意:数组初始化时,要指定数组的长度,因为只有确定了数组的长度之后,才能在内存中开辟所需要的空间。
并且数组一旦初始化完成,其长度就确定了。

2.2 调用数组指定位置的元素(通过下标调用)

System.out.println("id:"+ids[0]+",name:"+names[0]);
System.out.println("id:"+ids[1]+",name:"+names[1]);
System.out.println("id:"+ids[2]+",name:"+names[2]);
System.out.println("id:"+ids[3]+",name:"+names[3]);

2.3 获取数组的长度

通过length属性获取

System.out.println(ids.length); //4
System.out.println(names.length); //4

2.4 遍历数组元素

2.4.1 使用for循环遍历

for (int i=0;i<ids.length;i++){
    System.out.println(ids[i]);
}

2.4.2 使用foreach循环遍历

for (String name:names) {
    System.out.println(name);
}

2.5 数组元素的默认初始化值 2.5.1 对于基本数据类型而言,默认初始化值各有不同

//数组元素是整型(int short long byte):0
int[] arr1=new int[4];
for (int i=0;i<arr1.length;i++){
    System.out.println(arr1[i]);
}

System.out.println("-------------------");

short[] arr2=new short[4];
for (int i=0;i<arr2.length;i++){
    System.out.println(arr2[i]);
}

System.out.println("-------------------");

long[] arr3=new long[4];
for (int i=0;i<arr3.length;i++){
    System.out.println(arr3[i]);
}

System.out.println("-------------------");

byte[] arr4=new byte[4];
for (int i=0;i<arr4.length;i++){
    System.out.println(arr4[i]);
}

运行结果:

//数组元素是浮点型(double float):0.0
double[] arr5=new double[4];
for (int i=0;i<arr5.length;i++){
    System.out.println(arr5[i]);
}

System.out.println("-------------------");

float[] arr6=new float[4];
for (int i=0;i<arr6.length;i++){
    System.out.println(arr6[i]);
}

运行结果:

//数组元素是char型:0(表现为空)
char[] arr7=new char[4];
for (int i=0;i<arr7.length;i++){
    System.out.println(arr7[i]);
}

运行结果:

//数组元素是boolean型:false
boolean[] arr8=new boolean[4];
for (int i=0;i<arr8.length;i++){
    System.out.println(arr8[i]);
}

运行结果:

//数组元素是引用数据类型:null
String[] arr9=new String[4];
for (int i=0;i<arr9.length;i++){
    System.out.println(arr9[i]);
}

运行结果:

2.6 数组的内存解析

new出来的对象、数组都存放在堆中;
局部变量都存放在栈中。

1. int[] arr = new int[4];
2. arr1[1] = 1;
   arr1[2] = 2;
3. arr1 = new int[5];
4. System.out.println(arr1[1]);//0

当执行第1步时,会先在堆中开辟出数组所需要的内存空间,初始化值为0,如下图所示:

当执行第2步,为数组元素赋值时,如下图所示:

当执行第3步,会在堆中重新开辟新的内存空间,然后改变arr1的首地址指向,如下图所示:
当执行第4步,会输出新的内存空间的默认值,所以输出结果为0。

三、二维数组的使用

二维数组是以数组作为数组元素的数组,即“数组的数组”。
对于二维数组的理解,我们可以看成是一维数组array1又作为另一个一维数组array2的元素而存在。

3.1 数组的声明和初始化

3.1.1 静态初始化

静态初始化是指:数组的初始化和数组元素的赋值操作同时进行

int[][] arr1=new int[][]{{1,2,3},{4,5},{6,7,8}};

3.1.2 动态初始化

动态初始化是指:数组的初始化和数组元素的赋值操作分开进行

//动态初始化1
int[][] arr2=new int[2][2];
arr2[0][0]=1;
arr2[0][1]=2;
arr2[1][0]=3;
arr2[1][1]=4;

//动态初始化2
int[][] arr3=new int[2][];
//为数组中第一个元素赋值
arr3[0]=new int[2];
//为数组中第一个元素中的元素赋值
arr3[0][0]=1;
arr3[0][1]=2;
//为数组中第二个元素赋值
arr3[1]=new int[3];
//为数组中第二个元素中的元素赋值
arr3[1][0]=3;
arr3[1][1]=4;
arr3[1][2]=5;

3.2 调用数组指定位置的元素(通过下标调用)

System.out.println(arr2[1][0]);//3
//注意:使用动态初始化方式2时,必须先赋值才能调用,否则会报空指针异常
System.out.println(arr3[1][2]);//5

3.3 获取数组的长度

通过length属性获取

int[][] arr1=new int[][]{{1,2,3},{4,5},{6,7,8}};
//获取外层数组的长度
System.out.println(arr1.length);//3
//获取内层数组的长度
System.out.println(arr1[0].length);//3
System.out.println(arr1[1].length);//2
System.out.println(arr1[2].length);//3

3.4 遍历数组元素

使用嵌套for循环遍历

int[][] arr1=new int[][]{{1,2,3},{4,5},{6,7,8}};
for (int i=0;i<arr1.length;i++){
    for (int j=0;j<arr1[i].length;j++){
        System.out.print(arr1[i][j]+" ");
    }
    System.out.println();
}

遍历结果

3.5 二维数组元素的默认初始化值

规定:二维数组分为外层数组的元素,内层数组的元素
int[][] arr = new int[4][3];
外层元素: arr[0],arr[1],arr[2],arr[3]
内层元素: arr[0][0],arr[1][2]等


针对于动态初始化方式一:比如: int[][] arr = new int[4][3];
外层元素的初始化值为:地址值
内层元素的初始化值为:与一维数组初始化情况相同


针对于初始化方式二:比如: int[][] arr = new int[4][];
外层元素的初始化值为: null (因为数组是引用类型,默认值为null)
内层元素的初始化值为:不能调用,否则会报空指针异常。

//动态初始化方式一
int[][] arr4= new int[3][2];
System.out.println(arr4[0]);//[I@4554617c  [表示一维数组 I表示int类型 @4554617c表示首地址值
System.out.println(arr4[0][0]);//0

System.out.println("-------------------");

String[][] arr5= new String[3][2];
System.out.println(arr5[0]);//[Ljava.lang.String;@74a14482
System.out.println(arr5[0][0]);//null

运行结果:

//动态初始化方式二
int[][] arr6= new int[3][];
System.out.println(arr6[0]);//null (因为数组是引用类型,默认值为null)
System.out.println(arr6[0][0]);//Exception in thread "main" java.lang.NullPointerException

运行结果:

3.6 二维数组的内存解析

1. int[][] arr1 = new int[4][];
2. arr1[1] = new int[]{1,2,3};
3. arr1[2] = new int[4];
4. arr1[2][1] = 30;

当执行第1步时,会先在堆中开辟出数组所需要的内存空间,初始化值为null,如下图所示:

当执行第2步,为数组元素arr1[1]赋值时,如下图所示:

当执行第3步,为数组元素arr1[2]赋值时,如下图所示:

当执行第4步,为数组元素arr1[2][1]赋值时,如下图所示:

四、数组中常见的算法

4.1 数组的复制

public class ArrayTest {
    public static void main(String[] args) {
        //数组的复制
        String[] arr1=new String[]{"A","B","C","D","E"};
        String[] arr2=new String[arr1.length];
        for (int i=0;i<arr1.length;i++){
            arr2[i]=arr1[i];
        }
        //打印出复制后的数组
        for (int i=0;i<arr2.length;i++){
           System.out.println(arr2[i]);
        }
    }
}

运行结果:

4.2 数组的反转

public class ArrayTest2 {
    public static void main(String[] args) {
        //数组元素的反转
        String[] arr=new String[]{"A","B","C","D","E"};
        for (int i=0;i<arr.length/2;i++){ //相当于把A和E、B和D的位置颠倒一下
            String temp=arr[i];
            arr[i]=arr[arr.length-i-1];
            arr[arr.length-i-1]=temp;
        }
        //打印出反转后的数组
        for (int i=0;i<arr.length;i++){
           System.out.println(arr[i]);
        }
    }
}

运行结果:

4.3 数组的查找

4.3.1 线性查找

线性查找又称顺序查找,是一种最简单的查找方法,它的基本思想是从第一个记录开始,逐个比较记录的关键字,直到和给定的K值相等,则查找成功;若比较结果与文件中n个记录的关键字都不等,则查找失败。

public class ArrayTest3 {
    public static void main(String[] args) {
        //线性查找
        String[] arr=new String[]{"A","B","C","D","E"};
        String target="C"; //要查找的目标元素
        //定义一个标识符,用来表示是否查到了目标 false:没找到 true:查找到了
        boolean flag=false;
        for (int i=0;i<arr.length;i++){
            if(target.equals(arr[i])){
                System.out.println("查找到了目标元素,位置为:"+i);
                flag=true;
                break;
            }
        }
        if(flag=false){
            System.out.println("未查找到目标元素!");
        }
    }
}

运行结果:

4.3.2 二分法查找

二分法查找又称折半查找,二分法查找的基本思想是设数组中的元素从小到大有序地存放在数组中(注:二分法查找的关键,首先数组元素必须从小到大有序排列)

  1. 首先将给定值target与数组中间位置上元素的值(key)比较,如果相等,则查找成功;
  2. 否则,若target小,则在数组前半部分中继续进行二分法查找;
  3. 若target大,则在数组后半部分中继续进行二分法查找。

这样,经过一次比较就缩小一半的查找区间,如此进行下去,直到查找成功或查找失败。

public class ArrayTest4 {
    public static void main(String[] args) {
        //二分法查找
        int[] arr =new int[]{1,3,5,6,7,10,12,36,66,88};
        int target=12; //要查找的目标
        int head=0; //首索引
        int end=arr.length-1; //末索引
        //定义一个标识符,用来表示是否查到了目标 false:没找到 true:查找到
        boolean flag=false;
        while (head<=end){
            int middle=(head+end)/2; //中间位置的索引
            if(target==arr[middle]){
                System.out.println("查找到了目标元素,位置为:"+middle);
                flag=true;
                break;
            }else if(target<arr[middle]){
                end=middle-1;
            }else { //target>arr[middle]
                head=middle+1;
            }
        }

        if(flag=false){
            System.out.println("未查找到目标元素!");
        }
    }
}

运行结果:

4.4 数组的排序

4.4.1 冒泡排序

排序思想:

  1. 比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较为止。

排序方法演示

代码实现

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr =new int[]{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        //冒泡排序
        for (int i=0;i<arr.length-1;i++){ //外循环为排序趟数,n个数进行n-1趟
            //内循环为每趟比较的次数,第i趟比较n-i次
            for (int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){ //相邻元素比较,如果前一个元素比后一个大,则交换两者的位置
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        //输出排序后的数组
        for (int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
}

运行结果:

4.4.2 快速排序

快速排序是迄今为止所有内排序算法中速度最快的一种。它的基本思想是:任取待排序序列中的某个元素作为标准(也称为支点、界点一般取第一个元素),通过一次划分,将待排元素分为左右两个子序列,左子序列元素的排序码均小于基准元素的排序码,右子序列的排序码则大于或等于基准元素的排序码,然后分别对两个子序列继续进行划分,直至每一个序列只有一个元素为止。最后得到的序列便是有序序列。

排序方法演示

代码实现

public class QuickSort {
        public static void quickSort(int[] arr,int low,int high){
            int i,j,base;
            if(low>high){
                return;
            }
            i=low;
            j=high;
            //temp就是基准位
            base = arr[low];
            
            while (i<j) {
                //先看右边,依次往左递减
                while (base<=arr[j]&&i<j) {
                    j--;
                }
                //再看左边,依次往右递增
                while (base>=arr[i]&&i<j) {
                    i++;
                }
                //如果满足条件则交换
                if (i<j) {
                    int t = arr[j];
                    arr[j] = arr[i];
                    arr[i] = t;
                }
            }
            //最后将基准为与i和j相等位置的数字交换
            arr[low] = arr[i];
            arr[i] = base;
            //递归调用左半数组
            quickSort(arr, low, j-1);
            //递归调用右半数组
            quickSort(arr, j+1, high);
        }
        
        public static void main(String[] args){
            int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
            quickSort(arr, 0, arr.length-1);
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]+" ");
            }
        }
}

运行结果:

4.5 Arrays工具类的使用

java.util.Arrays类即为操作数组的工具类,包含了用来操作数组(比如排序和搜索)的各种方法。

4.5.1 boolean equals(int[] a,int[] b) 判断两个数组是否相等

//boolean equals(int[] a,int[] b) 判断两个数组是否相等
int[] arr1=new int[]{1,2,3,4,5};
int[] arr2=new int[]{1,3,5,7,9};
int[] arr3=new int[]{1,3,5,7,9};
boolean isEquals=Arrays.equals(arr1, arr2);
boolean isEquals2=Arrays.equals(arr2, arr3);
System.out.println(isEquals); //false
System.out.println(isEquals2); //true

运行结果:

4.5.2 String toString(int[] a) 输出数组信息

// String toString(int[] a) 输出数组信息
int[] arr1=new int[]{1,2,3,4,5};
System.out.println(Arrays.toString(arr1));

运行结果:

4.5.3 void fill(int[] a,int val) 将指定值填充到数组之中

int[] arr1=new int[]{1,2,3,4,5};
System.out.println(Arrays.toString(arr1)); //输出原数组
Arrays.fill(arr1,6); //将指定值填充到数组之中
System.out.println(Arrays.toString(arr1)); //输出用指定值填充过的数组

运行结果:

4.5.4 void sort(int[] a) 对数组进行排序

int[] arr1=new int[]{6,2,5,3,1,8};
Arrays.sort(arr1); //对数组进行排序
System.out.println(Arrays.toString(arr1)); //输出排序后的数组

运行结果:

4.5.5 int binarySearch(int[] a,int key) 对排序后的数组使用二分法检索指定的值

int[] arr1=new int[]{1,2,5,7,13,28,36};
int index=Arrays.binarySearch(arr1,7); //使用二分法检索指定的值,返回值为正数时,则为查找值的索引位置;返回值为负数,表示未查找到
System.out.println(index);

运行结果:

4.6 数组中常见的异常

数组也是Java中一个非常重要的知识点,无论是在日常开发还是面试和笔试中都经常用到。希望本篇文章能够对你有所帮助。


转载:https://blog.csdn.net/Mr_wxc/article/details/106797434
查看评论
* 以上用户言论只代表其个人观点,不代表本网站的观点或立场