向右轮转数组
给定一个整数数组 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 - 1
0 <= k <= 105
方法 1:使用额外数组
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> v(n); // 创建新的数组
for (int i = 0; i < n; i++) {
v[(i + k) % n] = nums[i]; // 将每个元素移动到新位置
}
nums = v; // 将新数组复制回原数组
}
};
理解 (i + k) % n
的含义:
i + k
:表示如果数组可以无限扩展,那么将当前元素 nums[i]
右移 k
步之后,它会移动到的位置。即这个元素在“扩展的数组”中的新索引。
因为数组的索引是循环的(最后一个位置的元素再移动一步就回到了第一个位置),我们需要取模操作来确保索引不超过数组的长度。因此i + k
可能会大于 n - 1
,此时我们通过 mod n
来将索引重新映射到 0 ~ n-1
这个范围内。取模的作用是让超出数组范围的索引“回到”数组的开头,形成环状循环。
方法 2:原地反转
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n; //取 k 对 n 的模,因为如果 k 大于 n,多余的旋转相当于重复旋转
reverse(nums.begin(), nums.end());// 反转整个数组
reverse(nums.begin(), nums.begin() + k);//反转前 k 个元素
reverse(nums.begin() + k, nums.end());//反转剩余的 n - k 个元素
}
};
思路:
- 将整个数组反转一次。
- 反转前
k
个元素。 - 反转剩下的
n - k
个元素。
举例说明:
例如对于数组 [1, 2, 3, 4, 5, 6, 7]
,k = 3
:
- 反转整个数组:
[7, 6, 5, 4, 3, 2, 1]
- 反转前 3 个元素:
[5, 6, 7, 4, 3, 2, 1]
- 反转剩下的元素:
[5, 6, 7, 1, 2, 3, 4]
原文地址:https://blog.csdn.net/Ct314/article/details/142686715
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!