解读

国内 Rust 面试中，这道题常被用来考察候选人对「所有权与借用检查」「Vec 内部布局」「算法稳定性」的综合理解。
面试官通常不会满足于“能跑就行”，而是追问：

1. 是否避免二次借用？
2. 是否保持元素相对顺序？
3. 时间复杂度是否O(n)？
4. 是否零额外堆分配？

若候选人直接循环 remove(i)，会因索引左移而越界或删错；若先 sort 索引再倒序删除，虽可行，但排序本身O(k log k) 且破坏原序。
高阶要求：在no_std 环境或**#[no_alloc]** 场景下仍能工作。

知识点

1. Vec::swap_remove
   把末尾元素换到被删位，O(1) 但打乱顺序。
2. Vec::remove
   保持顺序，O(n) 且会左移后续元素，导致后续索引失效。
3. Drain + Filter
   利用 Vec::retain 或自定义 Drain 迭代器，单遍扫描即可完成，无额外堆分配。
4. 索引去重与降序
   若必须物理删除且保序，可先收集索引→去重→降序→依次 remove，保证每个位置只被移动一次。
5. unsafe 边界
   面试官会追问：能否用 ptr::copy_nonoverlapping 手动压缩？需证明无别名、无重叠、生命周期合法；生产代码必须加 debug_assert + Miri 通过。

答案

推荐生产级方案：使用 retain 的闭包版本，零堆分配、保序、O(n)，且完全 safe。

/// 从 vec 中删除位于 `idxs` 内的所有元素，保持剩余元素原序。
/// 要求：`idxs` 中无重复且均合法（0 <= i < len）。
pub fn remove_indices<T>(vec: &mut Vec<T>, idxs: &[usize]) {
    use std::collections::HashSet;
    let fast_set: HashSet<usize> = idxs.iter().copied().collect();
    let mut i = 0;
    vec.retain(|_| {
        let keep = !fast_set.contains(&i);
        i += 1;
        keep
    });
}

复杂度：

• 时间：O(n)，单遍扫描。
• 空间：O(k)，k 为待删索引数，仅一次 HashSet 分配。

若索引已排序且无重复，可进一步优化为双指针，将 HashSet 换成位图或 Vec<bool>，在no_std + alloc 环境同样适用。

拓展思考

1. 稳定性与回滚
   若删除失败需事务级回滚，可先用 Vec::drain_filter（nightly）收集被删元素，批量移除；一旦中途出错，可将已删元素重新插入原位置（需记录原始偏移）。
2. 并行删除
   在多线程场景，可将 Vec 分片，每个线程本地计算待删掩码，最后单线程合并掩码并一次性压缩，避免锁竞争。
3. 零拷贝视图
   若数据量大且删除比例极低，可放弃物理删除，而是维护一个“逻辑删除”的 Bitmap，对外提供封装后的迭代器；这在嵌入式数据库或高频交易订单簿中常见，延迟物理回收到批量重建阶段。
4. const-eval 友好
   在const fn 场景（如内核静态数组），无法使用 HashSet，可改用排序 + 双指针在编译期完成索引过滤，实现const 级数组压缩。