前言#
今天这道题难度是中等的
题目#
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 10 <= k <= 105
进阶：
- 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
- 你可以使用空间复杂度为
O(1)的 原地 算法解决这个问题吗？
分析#
我们直接来看进阶的第二点，采用空间复杂度为O(1)的方式，也就是直接操作在原有数组中
这里有个点我之前一直没说，就是一维结果的数组，那么时间复杂度应该小于等于O(n)，所以一般我们得思考一个一次遍历的方式。
这道题其实很简单，就是一个从头出，然后从尾巴进入的方式，所以解法也很简单
解#
pub fn rotate(nums: &mut Vec<i32>, k: i32) {
if k <= 0 {
return;
}
let len = nums.len();
if len <= 0 {
return;
}
let t = k as usize % len;
for i in 0..t {
let num = nums[len - 1];
nums.pop();
nums.insert(0, num);
}
dbg!(&nums);
}取余是为了拿到最小移动的次数，因为等于len的时候就不需要动。
按理说这个解法时间复杂度应该是最小的了，但是提交的时候耗时需要359ms。。。应该是insert会影响整个数组下标的更新，所以需要大量的耗时。
所以我们来采用别的方案来优化下
优化#
其实这道题还有个很巧妙的解法，就是切割，切片成等长的不同组。
然后组里的元素和不同组同位置的元素轮换即可。
这里可能有些费解，我们来个例子分析下：
nums = [-1, -100, 3, 99, 88, 2333], k = 4。
它的正确输出是：
[3, 99, 88, 2333, -1, -100]
我们要怎么切呢？
根据k来切，如果k不能整切，那么就取数组长度和k的最大公因数，这样必定可以整切
比如我们的这个例子，它不能整除4，所以要取长度6和4的最大公因数，也就是2来切。
所以这个数组最终被切割为[-1, -100], [3, 99], [88, 2333]。
那么我们要处理这些组的时间复杂度就是O(2 * 3)，因为每个元素需要轮换3次,而每组只有俩元素
所以我们可以直接开始写代码了
先来实现获取最大公因数的：
fn get_common_factor (mut a: usize, mut b: usize) -> usize {
if b > a {
let q = a;
a = b;
b = q;
}
let mut t = a % b;
if t == 0 {
return b;
}
while t != 0 {
b = t;
t = a % t;
a = b;
}
a
}用循环或者递归都行。
然后我们来实现主体：
pub fn improve_rotate(nums: &mut Vec<i32>, k: i32) {
let len = nums.len();
if len <= 0 {
return
}
// 取最小一次循环
let p = k as usize % len;
// 如果最小循环和数组一样长，那就是不变
if p == 0 {
return;
}
// 找step
// 可以被整除的场景
let cycle = get_common_factor(len.clone(), p.clone());
let step = len / cycle;
dbg!(cycle);
dbg!(step);
// 每个切片包含的元素个数
for i in 0..cycle {
let mut target = nums[i];
// 每个元素需要交换step次
for j in 1..=step {
// 每个元素的间隔为p
// 拿出下次交换的家伙
let next_one = nums[(i + j * p) % len]; // 避免越界
// 开始替代
// 注意，这里是p，而不是p
nums[(i + j * p) % len] = target;
// 交换下，刷新下次交换的数据
target = next_one;
}
}
dbg!(&nums);
}这里没啥好说的了
测试用例#
#[cfg(test)]
mod tests {
use super::{ rotate, improve_rotate };
#[test]
fn test_rotate() {
assert_eq!(rotate(&mut [1, 2, 3, 4, 5, 6, 7].to_vec(), 3), ());
assert_eq!(rotate(&mut [-1, -100, 3, 99].to_vec(), 2), ());
}
#[test]
fn test_improve_rotate() {
assert_eq!(improve_rotate(&mut [1, 2, 3, 4, 5, 6, 7].to_vec(), 3), ());
assert_eq!(improve_rotate(&mut [-1, -100, 3, 99].to_vec(), 2), ());
}
}总结#
虽然我们pop和insert需要遍历的次数最少，但是我们耗时却很高，因为insert是插入到第一个元素，会影响到整个数组的下标更新，所以存在较高的耗时。
第二种方法需要我们脑子绕下弯，还是那句话，这种东西得有数理思维，没有，可能就绕不过去了。。。。