Rust数组旋转：低内存单循环方案为何耗时远高于多循环高内存方案？

嘿，这个问题问得特别实在！很多刚上手算法的朋友都会有这个误区：觉得代码越简洁、用的内存越少，运行速度就越快，但实际在处理像Vec这类动态数组的时候，很多“看起来简单”的操作背后藏着巨大的性能开销。咱们来拆解你的两个实现，就能明白为啥差距这么大了。

先看你的第一个实现（300ms版本）：

impl Solution {
    pub fn rotate(nums: &mut Vec<i32>, k: i32) {
        let i = nums.len() - 1;
        let mut x = 0;
        while x < k as usize {
            let e = nums[i];
            nums.remove(i);
            nums.insert(0, e);
            x = x+1;
        }
    }
}

你这里的核心操作是每次循环把最后一个元素移到开头，虽然代码只有几行，但每一次insert(0, e)都是O(n)复杂度的操作——因为Vec是连续内存存储的，要在开头插入元素，必须把从索引0到末尾的所有元素都往后挪动一位，才能腾出第一个位置放新元素。如果k是一个比较大的数（比如等于数组长度n），那这个循环的总时间复杂度就是O(k*n)=O(n²)，这在数组长度大的时候，开销会爆炸式增长。

再看那个更快的实现（10ms版本）：

impl Solution {
    pub fn rotate(nums: &mut Vec<i32>, k: i32) {
        let k: usize = k as usize;
        let length = nums.len();
        let mut n: usize = 1;
        while (((n * length - k) as i32) < 0) {
            n += 1;
        }
        let mut padding: usize = n * length - k;
        let mut res = Vec::with_capacity(length);
        for i in 0..length {
            res.push(nums[(i + padding) % length]);
        }
        for i in 0..length {
            nums[i] = res[i];
        }
    }
}

这个实现看起来代码多了点，但思路很聪明：它先通过计算padding处理了k大于数组长度的情况（其实更简洁的写法是let k = k % length，效果是一样的），然后直接通过模运算算出每个元素旋转后的目标位置，一次性把所有元素放到预先分配好容量的新Vec里，最后再复制回原数组。

这里的关键优势：

• 预先用with_capacity(length)创建res，避免了push过程中的内存扩容开销
• 所有操作都是线性遍历，总时间复杂度是O(n)，不管k多大，只需要遍历数组两次
• 连续内存的访问和拷贝是现代CPU最擅长的操作，效率远比多次零散的内存挪动高

说白了，你第一个方案的“低内存”是以指数级的时间开销为代价的，而第二个方案用一点点额外内存换来了线性时间，在算法题的测试场景下（尤其是大数组用例），这种时间上的优势会被无限放大，所以才会出现300ms和10ms的巨大差距。

备注：内容来源于stack exchange，提问作者monkeypotter