旋转数组 Rotate Array

问题描述

三次反转法

操作过程如下:

  1. 将 arr[k..n] 进行反转
  2. 将 arr[0..k] 进行反转
  3. 将 arr[..] 进行反转

这个方法是在原地操作的, 其时间复杂度是 O(n), 空间复杂度是 O(1).

#![allow(unused)]
fn main() {
/// 三次反转法
pub fn rotate2(nums: &mut Vec<i32>, k: i32) {
    // 检查边界条件
    if nums.is_empty() || k <= 0 {
        return;
    }
    let len: usize = nums.len();
    let k: usize = (k as usize) % len;
    if k == 0 {
        return;
    }

    // 第一步, 把所有元素做反转.
    nums.reverse();
    // 第二步, 找到右移的分界线 k, 把 [0..k] 做反转.
    nums[0..k].reverse();
    // 第三步, 把 [k..len] 做反转
    nums[k..].reverse();
}
}

使用时时数组

操作过程如下:

  1. 创建辅助数组
  2. 将 arr[(len - k)..] 复制到辅助数组
  3. 将 arr[..(len - k)] 复制到辅助数组
  4. 将辅助数组中的内容与目标数组交换, 通过 mem::swap()

这个方法不是在原地操作的, 其时间复杂度是 O(n), 空间复杂度是 O(n).

#![allow(unused)]
fn main() {
/// 使用临时数组
pub fn rotate3(nums: &mut Vec<i32>, k: i32) {
    if nums.is_empty() || k <= 0 {
        return;
    }
    let len = nums.len();
    let k = len - (k as usize) % len;
    if k == 0 {
        return;
    }

    let mut aux = Vec::with_capacity(len);
    aux.extend_from_slice(&nums[k..]);
    aux.extend_from_slice(&nums[..k]);
    mem::swap(nums, &mut aux);
}
}

参考