【数据结构】数组

数组

数组（Array），由相同数据类型的元素（element）的集合组成的数据结构，分配一块连续的内存来存储。

初始化

初始化一个数组（不给定初始值）：

// 创建一个名为arr的整数数组
int[] arr = new int[5];

// 上述语句分为两部分：
// 1. int[]：声明一个整数数组
// 2. new int[5]：使用new关键字创建一个包含5个整数元素的新数组

// 注意：数组索引从0开始，因此这个数组的有效索引范围是0到4（总共5个元素）

// 现在，arr是一个长度为5的整数数组，所有元素的初始值为0（基本数据类型的默认值）

初始化一个数组（给定初始值）：

// 创建一个名为nums的整数数组，并初始化数组元素
int[] nums = { 1, 3, 2, 5, 4 };

// 上述语句分为两部分：
// 1. int[]：声明一个整数数组
// 2. { 1, 3, 2, 5, 4 }：初始化数组元素，数组长度为5

// 注意：这种初始化方式在声明数组的同时为其赋初值

// 数组元素的含义：
// nums[0] = 1：数组的第一个元素（索引为0）的值为1
// nums[1] = 3：数组的第二个元素（索引为1）的值为3
// nums[2] = 2：数组的第三个元素（索引为2）的值为2
// nums[3] = 5：数组的第四个元素（索引为3）的值为5
// nums[4] = 4：数组的第五个元素（索引为4）的值为4

// 注意：数组索引从0开始，因此这个数组的有效索引范围是0到4（总共5个元素）

访问元素

在数组中访问元素非常高效，我们可以在 𝑂(1) 时间内随机访问数组中的任意一个元素。

// 定义一个方法randomAccess，该方法接收一个整数数组nums作为参数
int randomAccess(int[] nums) {

    // 生成一个随机索引，范围在数组长度内
    int randomIndex = ThreadLocalRandom.current().nextInt(0, nums.length);

    // 获取数组中随机索引对应的元素值
    int randomNum = nums[randomIndex];

    // 返回随机获取的数组元素值
    return randomNum;
}

// 方法说明：
// 1. randomIndex = ThreadLocalRandom.current().nextInt(0, nums.length)：
//    通过ThreadLocalRandom生成一个位于 [0, nums.length) 范围内的随机整数，用作数组的索引。

// 2. int randomNum = nums[randomIndex]：
//    通过随机生成的索引获取数组中对应索引位置的元素值，即随机访问数组中的一个元素。

// 3. return randomNum：
//    将随机获取的数组元素值作为方法的返回值。

插入元素

数组是一种存储固定大小元素的数据结构。数组的元素在内存中是连续存储的，也就是说，它们是"紧挨着的"。当你想在数组中间插入一个元素时，必须将该元素之后的所有元素都向后移动一位，再将待插入的元素插入到中间位置。

// 在数组 nums 的索引 index 处插入元素 num
void insert(int[] nums, int num, int index) {

    // 使用循环从数组末尾开始，将元素逐个向后移动，为新元素腾出插入位置
    for (int i = nums.length - 1; i > index; i--) {
        nums[i] = nums[i - 1];
    }

    // 在指定索引位置插入新元素
    nums[index] = num;
}

// 方法说明：
// 1. for (int i = nums.length - 1; i > index; i--)：
//    从数组末尾开始循环，将索引大于给定index的元素逐个向后移动，为新元素腾出插入位置。

// 2. nums[i] = nums[i - 1]：
//    将当前索引位置的元素的值设置为前一个索引位置的元素的值，实现向后移动。

// 3. nums[index] = num：
//    在指定索引位置插入新元素，将新元素的值赋给数组对应索引位置。

删除元素

与插入元素类似，如果你想删除数组中某一位置的元素，需要将后面的元素都向前移动一位。

删除元素后，原先末尾的元素就已经“无意义”了，因此不用特意修改。

// 删除数组 nums 中索引为 index 处的元素
void remove(int[] nums, int index) {

    // 使用循环从指定索引位置开始，将元素逐个向前移动，实现删除指定位置的元素
    for (int i = index; i < nums.length - 1; i++) {
        nums[i] = nums[i + 1];
    }
}

// 方法说明：
// 1. for (int i = index; i < nums.length - 1; i++)：
//    从指定索引位置开始循环，将索引大于等于给定index的元素逐个向前移动，实现删除指定位置的元素。

// 2. nums[i] = nums[i + 1]：
//    将当前索引位置的元素的值设置为后一个索引位置的元素的值，实现向前移动。

遍历数组

在Java中，遍历数组即可以通过索引来遍历，也可以通过for-each方式来遍历。

// 遍历数组
void traverse(int[] nums) {

    // 初始化一个计数器变量count，用于累加数组元素的值
    int count = 0;

    // 使用传统的for循环遍历数组
    for (int i = 0; i < nums.length; i++) {
        // 将当前索引位置的元素值累加到计数器
        count += nums[i];
    }

    // 使用增强型for循环（for-each）遍历数组
    for (int num : nums) {
        // 将当前元素值累加到计数器
        count += num;
    }
}

// 方法说明：
// 1. int count = 0;：
//    初始化一个计数器变量count，用于累加数组元素的值。

// 2. for (int i = 0; i < nums.length; i++)：
//    使用传统的for循环遍历数组，将每个索引位置的元素值累加到计数器。

// 3. for (int num : nums)：
//    使用增强型for循环（for-each）遍历数组，将每个元素值累加到计数器。

查找元素

在数组中查找特定的元素，可以通过一层循环，遍历数组元素，在每轮循环中判断当前数组元素是否为待查找的元素。若匹配，则输出对应索引，否则返回-1，代表查无此元素。

// 在数组 nums 中查找指定元素 target
int find(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            return i;
        }
    }
    return -1;
}

// 方法说明：
// 1. for (int i = 0; i < nums.length; i++)：
//    使用传统的for循环遍历数组，检查每个索引位置的元素是否等于目标整数。

// 2. if (nums[i] == target)：
//    判断当前索引位置的元素是否等于目标整数。

// 3. return i;：
//    如果找到目标整数，返回当前索引位置。

// 4. return -1;：
//    如果未找到目标整数，返回-1表示未找到。

数组扩容

在Java中，数组的长度是固定不可变的，一旦数组被创建后，其长度就不能更改。如果你需要扩容数组，通常的做法是创建一个新数组，并将原数组中的元素复制到新数组中。

举个例子，比如这里给定了一个旧数组 oldArray，然后创建了一个新数组 newArray（长度是旧数组长度的两倍），最后，将旧数组的元素复制到新数组中。

// 定义旧数组 oldArray，包含元素 1, 2, 3, 4, 5
int[] oldArray = {1, 2, 3, 4, 5};

// 创建新数组 newArray，长度是旧数组的两倍
int[] newArray = new int[oldArray.length * 2];

// 使用循环将旧数组的元素复制到新数组中
for (int i = 0; i < oldArray.length; i++) {
    // 将旧数组中的元素逐个复制到新数组的相同索引位置
    newArray[i] = oldArray[i];
}

当前，你也可以通过System.arraycopy 方法将一个数组的内容复制到另一个数组（适用于大规模数据的复制）

int[] oldArray = {1, 2, 3, 4, 5};
int[] newArray = new int[oldArray.length * 2];
System.arraycopy(oldArray, 0, newArray, 0, oldArray.length);
// oldArray：源数组，要从这个数组复制元素
// 0：源数组起始位置，从源数组的第0个元素开始复制
// newArray：目标数组，要将元素复制到这个数组
// 0：目标数组起始位置，从目标数组的第0个位置开始粘贴
// oldArray.length：要复制的元素个数，即源数组的长度

或者，也可以使用 Arrays.copyOf 方法来复制数组元素：

int[] oldArray = {1, 2, 3, 4, 5};
int newLength = oldArray.length * 2;

// Arrays.copyOf(原数组, 新数组的长度);
int[] newArray = Arrays.copyOf(oldArray, newLength);

数组的优点和局限性

数组是一种在编程中常用的数据结构，具有一些优点和一些局限性。

优点：

1. 快速访问： 数组中的元素通过索引直接访问，这使得对元素的访问速度非常快，支持随机访问，时间复杂度为 O(1)。
2. 内存连续： 数组中的元素在内存中是连续存储的，这有助于缓存性能的提升，空间效率高。
3. 简单易用： 数组的使用非常简单，适合存储和访问一组相同类型的元素。

局限性：

1. 固定大小： 数组在创建时需要指定固定的大小，这导致了无法动态调整数组的长度。如果需要动态大小的数据结构，可能需要使用其他集合类。
2. 插入和删除开销大： 在数组中插入或删除元素通常需要移动其他元素，这导致了较大的时间复杂度（O(n)）。
3. 浪费空间： 如果数组的大小超过实际需要的大小，会导致内存浪费。反之，如果数组太小，可能需要频繁地进行扩容操作。
4. 不适合频繁的查找和删除： 数组适用于快速访问，但对于频繁的查找和删除操作，可能不是最佳选择。

动态数组

在Java中，ArrayList 是一种动态数组，属于 java.util 包。

ArrayList与内置数组的区别在于，数组的大小无法修改（如果要向数组添加或删除元素，必须创建一个新数组）。而ArrayList可以随时添加和删除元素。当 ArrayList 的元素数量超过其当前容量时，ArrayList 会自动增加其容量。

也就是ArrayList帮你实现好了扩容，底层通过创建一个新的数组，将原数组的元素复制到新数组中来实现的。默认情况下，扩容时会将容量翻1.5倍。

ArrayList 是使用泛型实现的，可以存储任意类型的对象。在创建 ArrayList 时，可以指定元素的类型。

下面是 ArrayList 的常见用法：

1. 创建ArrayList对象：

import java.util.ArrayList;

ArrayList<String> cars = new ArrayList<String>();

2. 添加元素：

cars.add("Volvo");
cars.add("BMW");
cars.add("Ford");
cars.add("Mazda");

3. 访问元素：

String car = cars.get(0);

4. 修改元素：

cars.set(0, "Opel");

5. 删除元素：

cars.remove(0);

6. 清空ArrayList：

cars.clear();

7. 获取ArrayList大小：

int size = cars.size();

8. 遍历ArrayList：

使用for循环：

for (int i = 0; i < cars.size(); i++) {
  System.out.println(cars.get(i));
}

或使用for-each循环：

for (String car : cars) {
  System.out.println(car);
}

9. 排序ArrayList：

使用Collections.sort()方法：

Collections.sort(cars);  // 对字符串进行排序