VitePress

Appearance

数组 & Vec（顺序表） ​

宝贝乖乖～这一节我们用 Rust 的 Vec<T> 来对应「顺序表」。考研里顺序表的核心就是：随机访问快、插入删除中间慢、尾部摊还快。

1. 考研常考点 ​

  • 顺序表的时间复杂度：
    • 按下标访问：O(1)
    • 末尾 push/pop：摊还 O(1)
    • 在中间插入/删除：O(n)（需要整体搬移）
  • 顺序表 vs 链表：
    • 查找多、随机访问多 → 顺序表优势
    • 插入删除多（且位置已知）→ 链表优势（但 Rust 实现更麻烦）

2. Rust 里的 Vec 关键 API（刷题够用） ​

rust
let mut a: Vec<i32> = Vec::new();
a.push(10);
a.push(20);
assert_eq!(a.len(), 2);
assert_eq!(a[0], 10);

// pop
let x = a.pop();
assert_eq!(x, Some(20));

// insert/remove（中间操作是 O(n)）
a.insert(1, 99);
let y = a.remove(0);

// 迭代
for v in a.iter() {
    // v: &i32
}

for v in a.iter_mut() {
    // v: &mut i32
}

3. 扩容与摊还（考研理解点） ​

Vec 底层是连续内存：容量不够时会 重新申请更大空间 + 搬移。

  • 单次扩容代价高（O(n)），但不会每次都扩容
  • 所以“连续 push n 次”的总成本是 O(n)，平均一次就是 摊还 O(1)

刷题建议：如果你大概知道大小，用 with_capacity：

rust
let mut a: Vec<i32> = Vec::with_capacity(1_000_000);

4. 典型题型：原地删除（双指针） ​

题意：删除数组中等于 x 的元素，保持相对顺序。

思路：快慢指针。慢指针指向“下一个可写位置”。

rust
pub fn remove_x(nums: &mut Vec<i32>, x: i32) {
    let mut k = 0usize;
    for i in 0..nums.len() {
        if nums[i] != x {
            nums[k] = nums[i];
            k += 1;
        }
    }
    nums.truncate(k);
}

考点对照：

  • 时间：O(n)
  • 空间：O(1)（原地）

5. 小练习（宝贝做完发我） ​

  1. 用 Vec 实现一个函数：把数组右移 k 位（循环右移）。
  2. 合并两个有序数组（双指针）。

下一节我们讲 链表：为什么考研必须懂，但 Rust 里工程上通常不手写（以及刷题的更优替代）。