跳到主要内容

数组

数组是一种连续存储的线性数据结构，支持通过下标随机访问元素。

数组的特性​

优点：

  • 随机访问时间复杂度 O(1)
  • 缓存友好：由于内存连续，能够更好地利用 CPU 缓存（局部性原理）
  • 实现简单

缺点：

  • 大小固定（静态数组）
  • 插入和删除需要移动元素，O(n)
  • 可能存在内存碎片（大块连续内存申请困难）

寻址公式​

数组之所以能实现 O(1)O(1) 的随机访问，是因为它使用了 基地址 + 偏移量 的计算方式： Location(i)=BaseAddress+i×dataSizeLocation(i) = BaseAddress + i \times dataSize 其中 dataSize 是每个元素占用的字节数。

缓存局部性 (Cache Locality)​

由于 CPU 缓存是按 缓存行 (Cache Line) 加载的，连续的内存意味着当访问 arr[i] 时，其后的 arr[i+1] 等元素很有可能已经进入缓存。这使得处理数组的速度通常远快于处理链表。

数组的基本操作​

public class ArrayDemo {
    private int[] data;
    private int size;
    
    // 初始化
    public ArrayDemo(int capacity) {
        this.data = new int[capacity];
        this.size = 0;
    }
    
    // 获取元素 - O(1)
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return data[index];
    }
    
    // 设置元素 - O(1)
    public void set(int index, int value) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        data[index] = value;
    }
    
    // 插入元素 - O(n)
    public void insert(int index, int value) {
        if (size == data.length) {
            throw new IllegalStateException("Array is full");
        }
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        
        // 从后向前移动元素
        for (int i = size; i > index; i--) {
            data[i] = data[i - 1];
        }
        
        data[index] = value;
        size++;
    }
    
    // 删除元素 - O(n)
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        
        int removedValue = data[index];
        
        // 从前向后移动元素
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        
        size--;
        return removedValue;
    }
    
    // 查找元素 - O(n)
    public int find(int value) {
        for (int i = 0; i < size; i++) {
            if (data[i] == value) {
                return i;
            }
        }
        return -1;
    }
}

解释：

  • 数组的随机访问是通过基地址 + 偏移量实现的
  • 插入和删除需要移动元素，时间复杂度为 O(n)
  • 如果在末尾插入或删除，时间复杂度为 O(1)

动态数组​

动态数组可以在容量不足时自动扩容：

public class DynamicArray {
    private int[] data;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;
    
    public DynamicArray() {
        this.data = new int[DEFAULT_CAPACITY];
        this.size = 0;
    }
    
    public DynamicArray(int capacity) {
        this.data = new int[capacity];
        this.size = 0;
    }
    
    // 获取元素数量
    public int size() {
        return size;
    }
    
    // 获取容量
    public int capacity() {
        return data.length;
    }
    
    // 判断是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    
    // 在末尾添加元素 - 均摊 O(1)
    public void add(int value) {
        if (size == data.length) {
            resize(data.length * 2);  // 扩容为原来的 2 倍
        }
        data[size++] = value;
    }
    
    // 在指定位置插入 - O(n)
    public void add(int index, int value) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        
        if (size == data.length) {
            resize(data.length * 2);
        }
        
        // 移动元素
        for (int i = size; i > index; i--) {
            data[i] = data[i - 1];
        }
        
        data[index] = value;
        size++;
    }
    
    // 删除指定位置元素 - O(n)
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        
        int removed = data[index];
        
        // 移动元素
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        
        size--;
        
        // 缩容：当元素数量小于容量的 1/4 时，容量减半
        if (size > 0 && size == data.length / 4) {
            resize(data.length / 2);
        }
        
        return removed;
    }
    
    // 扩容/缩容
    private void resize(int newCapacity) {
        int[] newData = new int[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if (i < size - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

扩容策略分析：

  • 为什么扩容 2 倍？

    • 扩容 k 倍时，均摊时间复杂度为 O(1)
    • 2 倍是常用的平衡点，既避免频繁扩容，又不会浪费太多空间

  • 缩容条件：

    • 当元素数量小于容量的 1/4 时缩容
    • 不能在 1/2 时缩容，避免在边界处反复扩容和缩容（复杂度震荡）

经典数组问题​

1. 两数之和​

// 给定数组和目标值，找出和为目标值的两个数的索引
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    
    return new int[]{-1, -1};
}

2. 合并两个有序数组​

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1;      // nums1 有效元素末尾
    int j = n - 1;      // nums2 末尾
    int k = m + n - 1;  // 合并后末尾
    
    // 从后向前填充
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
    
    // 处理 nums2 剩余元素
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

练习​

  1. 实现一个支持动态扩容的数组
  2. LeetCode 1：两数之和
  3. LeetCode 88：合并两个有序数组
  4. LeetCode 283：移动零