LeetCode Rust - 189 - 轮转数组
解一，遍历推入新数组
按照：给定的下标处到数组末尾、从0到指定下标前 的顺序将元素推入到新数组
pub fn rotate(nums: &mut Vec<i32>, k: i32) {
if k == 0 { return }
let len = nums.len();
let _k = len - k as usize % len;
let mut res: Vec<i32> = vec![];
for i in _k..len {
res.push(nums[i]);
}
for i in 0.._k {
res.push(nums[i]);
}
*nums = res
}
时间 $O(n)$ 空间 $O(n)$
解二，数组翻转
假设有数组 [1, 2, 3, 4, 5, 6, 7] 且 k = 2：
- 先把数组整个翻转
[7, 6, 5, 4, 3, 2, 1] - 然后把前
k个项翻转[6, 7, 5, 4, 3, 2, 1] - 最后把剩余的项翻转，完成
[6, 7, 1, 2, 3, 4, 5]
pub fn rotate(nums: &mut Vec<i32>, k: i32) {
let len = nums.len();
let _k = k as usize % len;
if _k == 0 { return; }
fn reverse(target: &mut Vec<i32>, mut start: usize, mut end: usize) {
loop {
if start >= end { break }
target.swap(start, end);
start += 1;
end -=1;
}
}
reverse(nums, 0, len - 1);
reverse(nums, 0, _k - 1);
reverse(nums, _k, len - 1);
}
时间：$O(2n) = O(n)$ 空间：$O(1)$