java数组基础及面试题详解

黑白客

数组

• 数组的概述
• 数组的声明创建
  
  • 内存分析
  • 三种初始化
  • 数组的四个基本特点
  • 数组边界
    
• 数组的使用
• 多维数组
• Arrays类
  
  • 冒泡排序
    
• 稀疏数组
  

数组

数组的概述

 数组的定义

• 数组是想同类型数据的有序集合
• 数组描述的是相同类型的若干数据，按照一定的先后次序排列而成。
• 其中，每个数据称作一个数组的元素，每个数组元素可以通过一个下标来访问他们（数组的下标是从0开始的）

数组的声明创建

• 首先必须声明数组变量，才能在程序中使用。下面是声明数组变量的语法。

dataType[] arrayRefVar;//首选方法
dataType arrayRefVar[];//效果相同但不是首选方法。

在类型后面加[]是java所推荐的，之所以支持下面这种语法，是因为这种是c c++的语法。在早年为了让c c++的程序员快速上手java而支持的。

• java语言用new操作符来创建数组，语法如下：

  dataType[] arrayRefVar = new dataType[arraySize];

• 数组的元素是通过索引访问的，数组索引从0 开始。

• 获取数组长度：arrays.length

内存分析

• java内存分析：

  • 堆：存放new的对象和数组。可以被所有的线程共享，不会存放别的对象引用。

  • 栈：存放基本变量类型(会包含这个基本类型的具体数值)

  引用对象变量（会存放这个引用在堆里面的具体地址）

  • 方法区：可以被所有的线程共享

  包含了所有的class和static变量

  1. 声明数组：int[] array;是在栈中创建一块内存空间。
  2. 创建数组：array = new int[10]；是在堆中创建一块内存区域.将这块内存区域的地址放到刚刚栈中创建的内存空间中调用。同时这块内存空间会分成十份，默认值是0。如果创建的是double类型，默认值是0.0。String默认是null
  3. 给数组赋值：array[1] = 10;将堆中指定位置的数值设置为10。

三种初始化

• 静态初始化：声明+赋值

  int[] array = {1,2,3,4}

• 动态初始化： 包含默认初始化

  int[] array;

  array = new int[2];

• 默认初始化：

  数组是引用类型，它的元素相当于类的实例变量。因此数组一经分配空间，其中的每个元素也被按照实例变量同样的方式被隐式初始化

数组的四个基本特点

• 其长度是确定的。数组一旦被创建，它的大小就是不可以改变的。
• 其元素必须是相同类型，不允许出现混合类型。
• 数组中的元素可以是任何数据类型，包括基本类型和引用类型
• 数组变量属于引用类型，数组也可以看成是对象，数组中的每个元素相当于该对象的成员变量。数组本身就是对象，java中对象是在堆中的（所有被new出来的都存放在堆中）。因此无论数组保存原始类型还是其它对象类型，数组对象本身是在堆中的。

数组边界

• 下标的合法区间：[0,length-1]，如果越界就会报错；

  public static void main(String[] args){

  ​   int[] a = new int[2];

  ​   sout(a[2])

  }

  以上输出语句中就取了越界的下标。就会报错：

  ​   ArrayIndexOutOfBoundsException:数组下标越界异常！

数组的使用

• For-Each循环

  也就是利用增强for循环，jdk1.5新增的。但是没有下标。遍历方便，操作其中的数显得笨拙

  int[]  arrays = {1,2,3,4,5};

  for(int array : arrays){//遍历arrays数组

  sout(array);

  }

• 数组做方法入参，数组做返回值

  package com.wang.arraysDemo;
  
  /**
  * @Auther: 王海新
  * @Date: 2021/1/29 19:58
  * @Description: 数组的入参，和做返回值演示：反转数组
  */
  public class demo01 {
    public static void main(String[] args) {
        int[] arrays = {1,2,3,4,5};
        int[] resover = resover(arrays);
        for (int i : resover) {
            System.out.println(i);
        }
    }
  
    /**
     * @Description: 反转字符串
     * @Param:
     * @return:
     * @Author: 王海新
     * @Date:
     */
    private static int[] resover(int[] arrays) {
        int[] resvoer  = new int[arrays.length];
        for (int i = 0 , j = resvoer.length-1; i < arrays.length; i++ , j--) {
            resvoer[j] = arrays[i];
        }
        return resvoer;
    }
  
  }

多维数组

• 多维数组可以看成是数组的数组，比如二维数组就是一个特殊的一维数组，其每个元素都是一维数组。

• 二维数组

  int a[][][] [] = new int[2] [5];

• 解析以上二维数组a可以看成一个两行五列的数组。

  遍历数组：

  for(int i = 0 ; i < a.length ; i ++){

  ​   for(int j = 0 ; j < a[i].length; j ++){

  ​       sout(a[i] [j]);

  }

  }

Arrays类

• 学习Arrays类，“是为了避免重复造轮子”

• 数组的工具类java.util.Arrays

• 由于数组对象本身并没有什么方法可以供我们调用，但API中提供了一个工具类Arrays类供我们使用，从而可以对数据对象进行一些基本的操作。

• 查看jdk帮助文档

• Arrays类中的方法都是Static修饰的静态方法，在使用的时候我们可以直接通过类名来调用，而不用使用对象来调用。当然也可以用对象来调用，只是更麻烦。

• Arrays类功能

  • 给数组赋值：通过fill方法
  • 对数组排序：通过sort方法，按升序
  • 比较数组：通过equals方法比较数组中元素值是否相等。
  • 查找数组元素：通过binarySearch方法能对排序好的数组进行二分查找法操作。

  Arrays.fill(a,2,4,0);//就是将a数组中从2到4的位置填充为0。会将原来的覆盖掉。

冒泡排序

• 冒泡排序无疑是最为出名的排序算法之一，总共有八大排序！
• 冒泡的代码还是相当简单的，两层循环，外层冒泡轮数，里层依次比较。江湖中人 人尽皆知
• 我们看到嵌套循环，应该立马就可以得出这个算法的时间复杂度为O(n^2)。
• 思考如何优化？

import java.util.Arrays;

/**
 * @Auther: 王海新
 * @Date: 2021/1/30 12:13
 * @Description: 冒泡排序
 */
public class demo2 {
    public static void main(String[] args) {
        //定义一个数组
        int[] a = {2,6,3,56,1,6,9,4,6,8,3,7};
        //将需要排序的数组传递给实现冒泡排序的方法
        int[] sort = sort(a);
        //利用工具类Arrays。中的打印方法。打印数组元素
        System.out.println(Arrays.toString(sort));
    }

    private static int[] sort(int[] array) {
        //临时变量
        int temp = 0;
        //第一层循环：控制遍历次数。判定条件 - 1 是为了少循环一次。因为剩下最后一个数的时候。不需要在确认
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = false; //通过flag减少没有意义的比较。
            //第二层循环：控制变换位置。-1 是为了防止越界 下面 j + 1的时候。减i是减去确定下来的位置
            for (int j = 0; j < array.length-1-i; j++) {
                //如果前面的元素大于后面的，就进行换位
                if (array[j] > array[j + 1]) {
                    //利用临时变量，进行换位。
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = true;
                }
            }

            //这里就是优化部分。比较在排到一般的时候，并没有元素进行位置移动。就证明已经排序完成，不需要再进行下面的排序了。可以直接结束。
            //通过flag标识符判断每次循环是否进行了元素变位。
            if (flag == false) {
                break;
            }
        }
        return array;
    }
}

稀疏数组

• 需求：编写五子棋游戏中，有存盘退出和续上盘的功能
• 使用二维数组记录棋盘
• 分析问题：因为该二维数组的很多值都是默认值0，因此记录了很多没有意义的数据。

0   0   0   0   0   0   0   0   0   0   0
0   0   1   0   0   0   0   0   0   0   0
0   0   0   2   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0

• 解决：稀疏数组

就是一个n行三列的数组。只记录不是默认数据的位置。

第一列代表原数组的列，

第二列代表原数组的行，

第三列代表值。

每一行代表一个元素。

除了第一行代表原数组有多少行，多少列，多少有效数字。

稀疏数组
11  11  2
1      2     1
2      3     2

解决方案如下：

package com.wang.arraysDemo;

/**
 * @Auther: 王海新
 * @Date: 2021/1/30 17:56
 * @Description: 稀疏数组  五子棋的存盘退出和续上盘功能
 */
public class demo3 {
    public static void main(String[] args) {
        //创建一个11 * 11 的棋盘。0表示没有棋子，1表示黑棋，2表示白棋
        int[][] array1 = new int[11][11];
        //假设下面是下的棋
        array1[1][2] = 1;
        array1[2][3] = 2;
        System.out.println("输出原始数组(棋盘）");
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array1[i].length; j++) {
                System.out.print(array1[i][j]+"\t");
            }
            System.out.println();
        }
        //转化为稀疏数组保存
        //获取有效值的个数
        System.out.println("==================");
        int sum = 0;
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array1[i].length; j++) {
                if (array1[i][j] != 0) {
                    sum ++;
                }
            }
        }
        System.out.println("有效值的个数"+ sum);

        //2.创建一个稀疏数组的数组
        int[][] array2 = new int[sum+1][3];
            //第一行保存原来数组有多少行，多少列，多少有效值
        array2[0][0] = 11;//多少行
        array2[0][1] = 11;//多少列
        array2[0][2] = sum;//多少有效值
        //遍历二维数组，将非零的值，存放到稀疏数组中
        int count = 0; //表示在稀疏数组中的行。
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array1[i].length; j++) {
                if (array1[i][j] != 0) {
                    count ++;
                    array2[count][0] = i;
                    array2[count][1] = j;
                    array2[count][2] = array1[i][j];
                }
            }
        }
        //输出稀疏数组
        System.out.println("稀疏数组");
        for (int i = 0; i < array2.length; i++) {
            System.out.println(array2[i][0]
                    + "\t" +array2[i][1]
                    + "\t" +array2[i][2]
            );
        }

        System.out.println("==================");
        /*还原数组*/
        System.out.println("还原数组");
        //1.读取稀疏数组
        int[][] array3 = new int[ array2[0][0] ][ array2[0][1] ];
        //2.还原其中的值
        for (int i = 1; i < array2.length; i++) {
            array3[ array2[i][0] ][ array2[i][1] ] = array2[i][2];
        }
        //3.打印
        System.out.println("还原原始数组(棋盘）");
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array1[i].length; j++) {
                System.out.print(array1[i][j]+"\t");
            }
            System.out.println();
        }

    }

}

结果：

输出原始数组(棋盘）
0   0   0   0   0   0   0   0   0   0   0   
0   0   1   0   0   0   0   0   0   0   0   
0   0   0   2   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
==================
有效值的个数2
稀疏数组
11  11  2
1   2   1
2   3   2
==================
还原数组
还原原始数组(棋盘）
0   0   0   0   0   0   0   0   0   0   0   
0   0   1   0   0   0   0   0   0   0   0   
0   0   0   2   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   
0   0   0   0   0   0   0   0   0   0   0   

Process finished with exit code 0

BlueMoonWolf

多谢分享。。。。
补个jdk8补充的方法.Arrays.parallelPrefix..
这个1.8增加的方法挺有趣的，并行处理数组中的项给予指定的操作。。对数组的每一项都进行同样的操作，好像涉及的prefix scan的算法，挺有趣的
可以参考下这个文章：
https://stackoverflow.com/questions/52961981/how-does-newly-introduced-arrays-parallelprefix-in-java-8-work/52962054


另外是1.8增加了stream的操作，array也可以使用这类方式操作的。。所以对应也可以了解下stream的东西

小丑恶人

厉害了大佬

黑白客

BlueMoonWolf 发表于 2021-1-30 20:49
多谢分享。。。。
补个jdk8补充的方法.Arrays.parallelPrefix..
这个1.8增加的方法挺有趣的，并行处理数 ...

感谢您的补充