数组（Array）

数组概述

数组用于保存一组类型相同的数据。数组中的每个数据称为元素，每个元素都有对应的索引。

Java 数组具有以下特点：

• 数组只能保存同一种数据类型的元素。
• 数组创建后长度固定，不能直接改变。
• 数组可以通过索引快速访问元素。
• 数组中间插入或删除元素时，通常需要移动其他元素。

需要扩大数组容量时，通常创建一个更大的新数组，再把原数组中的元素复制过去。

一维数组

数组变量的定义

推荐把方括号写在数据类型后面：

int[] numbers;
double[] prices;
String[] names;

也可以把方括号写在变量名后面，但不推荐这种写法。

int numbers[];

数组属于引用类型。

数组的创建

一维数组的静态初始化

静态初始化是在声明数组变量时直接指定元素值，数组长度由元素数量决定。

int[] numbers = {2, 5, 7, 8};

也可以写出完整形式：

int[] numbers = new int[] {2, 5, 7, 8};

省略 new int[] 的简写形式只能在声明变量的同时使用。

一维数组的动态初始化

动态初始化先指定数组长度，由系统为各元素设置默认值。

int[] numbers = new int[3];

不同类型数组元素的默认值如下：

数组的内存模型

基本类型变量直接保存基本类型值；引用类型变量保存对象的引用。引用变量的具体内存大小由 JVM 实现和运行模式决定，不能简单认为固定为某个字节数。

null 表示引用变量当前没有指向任何对象，只能赋给引用类型变量。

String text = null;
int[] numbers = null;

数组对象创建后位于堆内存中，数组变量保存该数组对象的引用。

String[] names = new String[] {"ab", "cd", "e"};

访问数组元素

数组索引从 0 开始，最大索引为 array.length - 1。

int[] numbers = {3, 5, 6, 4, 25, 7, 3, 8, 9};

System.out.println(numbers[0]);
numbers[0] = 30;
System.out.println(numbers[numbers.length - 1]);

访问不存在的索引会抛出 ArrayIndexOutOfBoundsException。

遍历数组

使用普通 for 循环

int[] numbers = {3, 5, 6, 4, 25, 7, 3, 8, 9};

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

普通 for 循环可以同时获得索引和元素值。

使用增强 for 循环

for (int number : numbers) {
    System.out.println(number);
}

增强 for 循环适合只读取元素值的场景，不能直接获得当前索引。

最大值、最小值与求和

数组为空时不能直接读取第一个元素，因此下面的写法要求数组至少包含一个元素。

int[] numbers = {3, 5, 6, 4, 25, 7, 3, 8, 9};
int max = numbers[0];
int min = numbers[0];
int sum = 0;

for (int number : numbers) {
    if (number > max) {
        max = number;
    }
    if (number < min) {
        min = number;
    }
    sum += number;
}

查找元素

Scanner scanner = new Scanner(System.in);
int target = scanner.nextInt();
int[] numbers = {3, 5, 6, 4, 25, 7, 3, 8, 9};
boolean found = false;

for (int number : numbers) {
    if (number == target) {
        found = true;
        break;
    }
}

System.out.println(found ? "有" : "没有");

数组拷贝

下面的代码把原数组元素按相反顺序复制到新数组中。

int[] source = {3, 5, 6, 4, 25, 7, 3, 8, 9};
int[] target = new int[source.length];

for (int i = 0; i < source.length; i++) {
    target[i] = source[source.length - 1 - i];
}

排序

选择排序

int[] numbers = {3, 5, 6, 4, 25, 7, 2, 8, 9, 11};

for (int i = 0; i < numbers.length - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < numbers.length; j++) {
        if (numbers[j] < numbers[minIndex]) {
            minIndex = j;
        }
    }

    if (minIndex != i) {
        int temp = numbers[i];
        numbers[i] = numbers[minIndex];
        numbers[minIndex] = temp;
    }
}

冒泡排序

int[] numbers = {3, 5, 6, 4, 25, 7, 2, 8, 9, 11};

for (int i = 0; i < numbers.length - 1; i++) {
    boolean swapped = false;
    for (int j = 0; j < numbers.length - 1 - i; j++) {
        if (numbers[j] > numbers[j + 1]) {
            int temp = numbers[j];
            numbers[j] = numbers[j + 1];
            numbers[j + 1] = temp;
            swapped = true;
        }
    }

    if (!swapped) {
        break;
    }
}

实际开发中通常直接使用 Arrays.sort()。

随机数

Random 类

nextInt(bound) 生成从 0 到 bound - 1 的整数。

Random random = new Random();

int number1 = random.nextInt(10);     // 0～9
int number2 = random.nextInt(6) + 5;  // 5～10

下面的代码使用 Fisher-Yates 思路打乱数组，比每次与任意位置交换更均匀。

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

for (int i = numbers.length - 1; i > 0; i--) {
    int index = random.nextInt(i + 1);
    int temp = numbers[i];
    numbers[i] = numbers[index];
    numbers[index] = temp;
}

Math.random()

Math.random() 返回大于等于 0.0 且小于 1.0 的 double 值。

int number1 = (int) (Math.random() * 10);      // 0～9
int number2 = (int) (Math.random() * 6) + 5;  // 5～10
int number3 = (int) (Math.random() * 11) - 5; // -5～5

二维数组

二维数组的定义

二维数组的元素仍然是一维数组，因此 Java 的二维数组本质上是“数组的数组”。

int[][] matrix;

也可以写成下面的形式，但不推荐：

int matrix[][];

二维数组的创建

二维数组的静态初始化

静态初始化是在创建数组的同时为数组元素赋值。

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

也可以写出完整形式：

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

第一个数组的外层长度为 3，三个内层数组的长度分别为 3、3、2。

二维数组的动态初始化

只创建外层数组

int[][] matrix = new int[3][];

这段代码只创建了一个长度为 3 的外层数组。此时 matrix[0]、matrix[1]、matrix[2] 都是 null，内层数组尚未创建，因此一共只创建了一个数组对象。

可以分别创建不同长度的内层数组，从而形成不规则二维数组。

matrix[0] = new int[2];
matrix[1] = new int[4];
matrix[2] = new int[1];

同时创建外层数组和内层数组

int[][] matrix = new int[3][2];

这段代码创建了一个长度为 3 的外层数组，以及三个长度为 2 的内层数组，共创建了四个数组对象。

它等价于先创建外层数组，再分别创建三个内层数组：

int[][] matrix = new int[3][];
for (int i = 0; i < matrix.length; i++) {
    matrix[i] = new int[2];
}

二维数组元素的访问

使用两个索引访问二维数组元素。第一个索引定位内层数组，第二个索引定位该内层数组中的元素。

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

System.out.println(matrix[1][2]); // 5

访问元素前要确保内层数组不为 null，并且两个索引都没有越界。

二维数组的遍历

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

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

也可以使用增强 for 循环：

for (int[] row : matrix) {
    for (int value : row) {
        System.out.println(value);
    }
}

二维数组的查找

int[][] matrix = {
    {1, 2},
    {3, 4, 5}
};
int target = 4;
boolean found = false;

outer:
for (int[] row : matrix) {
    for (int value : row) {
        if (value == target) {
            found = true;
            break outer;
        }
    }
}

System.out.println(found ? "有" : "没有");

二维数组的深拷贝

仅复制外层数组会使新旧二维数组共享内层数组。要实现独立副本，需要继续复制每个内层数组。

int[][] source = {
    {1, 2},
    {3, 4, 5}
};
int[][] target = new int[source.length][];

for (int i = 0; i < source.length; i++) {
    target[i] = Arrays.copyOf(source[i], source[i].length);
}

不规则二维数组

Java 允许各内层数组长度不同。

int[][] matrix = new int[3][];
matrix[0] = new int[] {1, 2};
matrix[1] = new int[] {3, 4, 5};
matrix[2] = new int[] {6};

遍历不规则二维数组时，应使用当前内层数组的 length，不能假设每一行长度相同。

Arrays 工具类

复制数组

int[] source = {4, 3, 2, 6, 7, 9, 1, 10, 11};
int[] copy = Arrays.copyOf(source, source.length);

Arrays.copyOfRange() 的结束索引不包含在复制范围内。

int[] part = Arrays.copyOfRange(source, 0, 5);

排序数组

int[] numbers = {4, 3, 2, 6, 7, 9, 1, 10, 11};
Arrays.sort(numbers);

二分查找

Arrays.binarySearch() 要求数组已经按相同规则排序。找到元素时返回非负索引，未找到时返回负数。

int[] numbers = {4, 3, 2, 6, 7, 9, 1, 10, 11};
Arrays.sort(numbers);

if (Arrays.binarySearch(numbers, 8) >= 0) {
    System.out.println("有");
} else {
    System.out.println("没有");
}

System.arraycopy()

System.arraycopy() 可以把源数组指定范围复制到目标数组的指定位置。

int[] source = {1, 2, 3, 4, 5, 6, 7};
int[] target = new int[10];

System.arraycopy(source, 2, target, 4, 2);
System.out.println(Arrays.toString(target));

上面的代码把源数组索引 2、3 位置的元素复制到目标数组索引 4、5 位置。