enyang

Menu

enyang
enyang
Published on 2025-11-25 / 7 Visits
0
0

数据结构<1>——数组

#Data Structures

1. 数组的定义

数组 是一种线性数据结构，它包含一个固定大小的、相同类型的元素集合。数组通过一个单一的名字来访问，并且元素通过索引来进行定位。每个数组都有一个特定的大小，一旦创建，大小不可改变。

  • 内存模型：数组是一个连续的内存空间，元素按顺序排列。

  • 特点：

    • 固定大小：数组创建时必须指定大小，不能动态增长（尽管Java提供了 ArrayList 来动态处理）。

    • 同类型元素：数组中的每个元素必须是相同类型，可以是基本数据类型（如int, char, double等），也可以是对象类型（如String, CustomClass等）。

    • 通过索引访问：可以通过数组的索引快速访问元素，索引从0开始。

2. 数组的基本操作

常用的数组操作包括创建、访问、更新、插入、删除等。

2.1 创建数组

在Java中，创建数组有两种方式：

  • 静态数组创建（声明时直接初始化）：

    int[] arr = {1, 2, 3, 4, 5}; // 创建一个包含5个元素的数组

  • 动态数组创建（使用 new 关键字）：

    int[] arr = new int[5]; // 创建一个包含5个元素的数组，初始值为0

2.2 访问数组元素

数组的元素是通过索引来访问的。索引从0开始，因此：

  • 第一个元素：arr[0]

  • 第二个元素：arr[1]

  • 最后一个元素：arr[arr.length - 1]

public class ArrayAccess {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        
        // 访问数组中的元素
        System.out.println(arr[0]);  // 输出 10
        System.out.println(arr[4]);  // 输出 50
    }
}

2.3 更新数组元素

更新数组元素的操作是通过指定索引来进行的：

arr[0] = 100; // 将第一个元素更新为100
public class ArrayUpdate {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        
        // 更新数组元素
        arr[2] = 10; // 将索引2的元素（即3）更新为10
        
        // 输出更新后的数组
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

2.4 数组的插入与删除

在固定大小的数组中，插入和删除元素相对复杂，因为：

  • 插入：如果你要在数组的中间插入元素，需要将后面的元素都移动到下一个位置。

  • 删除：删除元素时，同样需要将后面的元素向前移动。

例如，在数组的中间插入一个元素：

// 在索引2处插入元素20
for (int i = arr.length - 1; i > 2; i--) {
    arr[i] = arr[i - 1]; // 向后移动
}
arr[2] = 20; // 插入20

public class ArrayInsertDelete {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        
        // 在数组索引2处插入元素20
        for (int i = arr.length - 1; i > 2; i--) {
            arr[i] = arr[i - 1];
        }
        arr[2] = 20;
        
        // 输出插入后的数组
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

删除操作：

// 删除索引2的元素
for (int i = 2; i < arr.length - 1; i++) {
    arr[i] = arr[i + 1]; // 向前移动
}
arr[arr.length - 1] = 0; // 最后一个元素置为0

2.5 数组的遍历

可以通过 for 循环、增强型for 循环来遍历数组：

// 普通for循环
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}

// 增强for循环（foreach）
for (int num : arr) {
    System.out.println(num);
}

示例代码：

public class ArrayTraversal {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        
        // 使用普通for循环
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        
        // 使用增强for循环
        for (int num : arr) {
            System.out.println(num);
        }
    }
}

3. 数组的优缺点

3.1 优点

  • 快速访问：通过索引，可以在常数时间（O(1)）内访问任何元素。

  • 内存连续：数组中的元素是连续存储的，这使得访问和操作非常高效。

  • 易于实现：数组操作简单，直接用索引就可以完成访问、插入、删除等操作。

3.2 缺点

  • 固定大小：数组的大小在创建时确定，无法动态调整大小。如果数组满了，需要创建一个新的、更大的数组并复制原数组的元素，这会带来额外的开销。

  • 插入和删除效率低：对于中间插入和删除操作，必须移动数组中的其他元素，因此时间复杂度为O(n)。

  • 内存浪费：如果数组预分配了大量空间，但实际只用到部分元素，剩余空间会浪费。

4. 数组的扩展：动态数组与 ArrayList

Java 提供了 ArrayList 类，它实现了动态数组的功能，可以在数组大小不够时自动扩展。

  • 动态扩展：ArrayList 会自动调整大小，当数组满时，它会自动创建一个更大的数组，并将元素复制到新数组中。通常扩展的规则是将原来的大小加倍。

import java.util.ArrayList;

public class DynamicArray {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        
        // 添加元素
        list.add(10);
        list.add(20);
        list.add(30);
        
        // 遍历
        for (int num : list) {
            System.out.println(num);
        }
    }
}

ArrayList 提供了常用的操作，如：

  • add(E e)：添加元素。

  • remove(int index)：删除元素。

  • get(int index)：访问元素。

5. 二维数组 (2D Array)

二维数组可以看作是数组的数组。例如，一个3x3的二维数组包含3个子数组，每个子数组包含3个元素。二维数组的创建、访问和操作与一维数组类似。

定义：

int[][] arr = new int[3][3]; // 创建一个3x3的二维数组

访问：

arr[0][1] = 5; // 设置第0行，第1列的元素为5
System.out.println(arr[0][1]); // 输出 5

遍历二维数组：

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

6. 数组常见问题

6.1 数组越界（ArrayIndexOutOfBoundsException）

  • 当访问数组中不存在的索引时，会抛出 ArrayIndexOutOfBoundsException。

int[] arr = {1, 2, 3};
System.out.println(arr[3]); // 索引3不存在，会抛异常

  • 防止方法：

    • 遍历数组时，使用 arr.length 作为循环条件。

    • 访问索引前进行判断：

if (index >= 0 && index < arr.length) {
    System.out.println(arr[index]);
}

6.2 数组内存消耗

  • 问题：数组大小固定，如果分配过大，可能浪费内存；如果分配过小，可能无法存储足够数据。

  • 解决方法：

    • 使用 动态数组（如 ArrayList）来按需扩展。

    • 对于稀疏数据（大部分为0或null），可使用 稀疏数组 或 Map 来节省空间。

6.3 数组拷贝

  • Java 中数组是引用类型，直接赋值只是拷贝引用，而不是元素。

int[] arr1 = {1, 2, 3};
int[] arr2 = arr1; // arr2指向同一个数组
arr2[0] = 100;
System.out.println(arr1[0]); // 输出 100

  • 正确拷贝方法：

    • 使用 Arrays.copyOf：

int[] arr2 = Arrays.copyOf(arr1, arr1.length);

  • 使用 System.arraycopy：

System.arraycopy(arr1, 0, arr2, 0, arr1.length);

6.4 数组排序

  • Java 提供了 Arrays.sort() 方法对数组进行排序。

int[] arr = {5, 2, 9, 1};
Arrays.sort(arr); // 升序排序
System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 5, 9]

  • 对对象数组可以通过自定义比较器排序：

String[] arr = {"apple", "orange", "banana"};
Arrays.sort(arr, (a, b) -> a.length() - b.length());
System.out.println(Arrays.toString(arr)); // 按字符串长度排序

6.5 数组搜索

  • 线性搜索（Linear Search）：

int target = 3;
int index = -1;
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) {
        index = i;
        break;
    }
}
System.out.println(index); // 输出目标索引

  • 二分搜索（Binary Search）（数组必须有序）：

int[] arr = {1, 2, 3, 4, 5};
int index = Arrays.binarySearch(arr, 3);
System.out.println(index); // 输出 2

6.6 数组反转

  • 方法1：双指针交换

int[] arr = {1, 2, 3, 4, 5};
int left = 0, right = arr.length - 1;
while (left < right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    left++;
    right--;
}
System.out.println(Arrays.toString(arr)); // 输出 [5, 4, 3, 2, 1]

  • 方法2：使用 Collections.reverse（对于包装类数组或列表）

Integer[] arr = {1, 2, 3, 4, 5};
List<Integer> list = Arrays.asList(arr);
Collections.reverse(list);
System.out.println(list); // 输出 [5, 4, 3, 2, 1]

6.7 多维数组问题

二维或多维数组在内存中是数组的数组，行长度可以不同（不一定是矩形）。

int[][] arr = new int[3][];
arr[0] = new int[2]; // 第一行有2个元素
arr[1] = new int[3]; // 第二行有3个元素
arr[2] = new int[1]; // 第三行有1个元素

  • 遍历二维数组：

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

6.8 数组常见优化

  1. 使用双指针解决子数组问题、数组排序或合并问题。

  2. 前缀和/差分数组用于快速求区间和。

  3. 滑动窗口用于求最大/最小子数组、连续和问题。

  4. 空间优化：对于一些算法，可用原地操作，避免额外数组开销。

7. 数组高级操作

7.1 数组旋转

  • 问题：将数组中的元素循环移动k个位置。

  • 方法1：暴力旋转

int[] arr = {1, 2, 3, 4, 5};
int k = 2; // 向右旋转2步
int n = arr.length;
int[] temp = new int[n];
for (int i = 0; i < n; i++) {
    temp[(i + k) % n] = arr[i];
}
arr = temp;
System.out.println(Arrays.toString(arr)); // 输出 [4, 5, 1, 2, 3]

  • 方法2：三次反转法（空间复杂度O(1)）

    1. 反转整个数组。

    2. 反转前k个元素。

    3. 反转剩余元素。

int[] arr = {1, 2, 3, 4, 5};
int k = 2;
reverse(arr, 0, arr.length - 1);
reverse(arr, 0, k - 1);
reverse(arr, k, arr.length - 1);

private static void reverse(int[] arr, int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

7.2 数组去重

  • 问题：删除数组中重复的元素。

  • 方法1：排序 + 双指针

int[] arr = {1, 2, 2, 3, 4, 4, 5};
Arrays.sort(arr);
int j = 0;
for (int i = 1; i < arr.length; i++) {
    if (arr[i] != arr[j]) {
        j++;
        arr[j] = arr[i];
    }
}
int newLength = j + 1;
System.out.println(Arrays.toString(Arrays.copyOf(arr, newLength))); // 输出 [1, 2, 3, 4, 5]

  • 方法2：使用 HashSet

int[] arr = {1, 2, 2, 3, 4, 4, 5};
Set<Integer> set = new HashSet<>();
for (int num : arr) {
    set.add(num);
}
System.out.println(set); // 输出 [1, 2, 3, 4, 5]

7.3 数组求和/前缀和

  • 前缀和：预处理数组，使得求区间和更快。

int[] arr = {1, 2, 3, 4, 5};
int[] prefixSum = new int[arr.length + 1];
prefixSum[0] = 0;
for (int i = 0; i < arr.length; i++) {
    prefixSum[i + 1] = prefixSum[i] + arr[i];
}
// 区间和 arr[1..3] = prefixSum[4] - prefixSum[1] = 2+3+4 = 9
System.out.println(prefixSum[4] - prefixSum[1]); // 输出 9

8. 数组的应用场景

数组不仅是基础数据结构，也是算法的核心载体：

  1. 排序算法：

    • 冒泡排序、选择排序、插入排序

    • 高级排序：快速排序、归并排序、堆排序

    • 示例：排序成绩、用户年龄列表

  2. 搜索算法：

    • 线性搜索：O(n)

    • 二分搜索：O(log n)，数组必须有序

    • 示例：查找指定学生ID或商品编号

  3. 滑动窗口问题：

    • 求连续子数组的最大值/最小值/和

    • 示例：最大子数组和问题、股票买卖最大利润

  4. 动态规划基础：

    • 数组可存储状态，如 Fibonacci、背包问题

    int[] dp = new int[n];
dp[0] = 1; dp[1] = 1;
for (int i = 2; i < n; i++) {
    dp[i] = dp[i-1] + dp[i-2]; // Fibonacci
}

  5. 矩阵问题：

    • 二维数组用于图像处理、地图寻路（BFS/DFS）

    • 示例：迷宫求最短路径

  6. 缓存和哈希表底层实现：

    • 哈希表、LRU缓存、布隆过滤器底层都用数组作为存储单元

9. 数组优化技巧

9.1 空间优化

  • 对于一些动态规划问题，可以用滚动数组减少空间：

int a = 1, b = 1;
for (int i = 2; i < n; i++) {
    int temp = a + b;
    a = b;
    b = temp;
}

  • 避免使用多维数组时的额外空间，使用一维数组即可。

9.2 时间优化

  • 双指针技巧：

    • 用于有序数组去重、两数之和、三数之和

int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) break;
    else if (sum < target) left++;
    else right--;
}

  • 前缀和 + 哈希表：

    • 用于求连续子数组和、子数组最大平均值问题

9.3 避免重复操作

  • 对于频繁访问数组元素的算法，尽量减少重复计算

  • 使用缓存、前缀和、差分数组等优化

9.4 边界条件处理

  • 空数组、长度为1、长度为2的特殊情况

  • 避免索引越界、负数索引

  • 在算法中使用 arr.length 而不是硬编码索引

数据结构<2>——链表
Git<1>——原理

Comment