个人新闻类网站模板,长沙企业建站招聘信息,常州模板建站代理,网站服务器 购买时长链接轮转数组题序号189题型数组解法1. 额外数组法#xff0c;2. 原数组翻转法#xff08;三次翻转法#xff09;难度中等熟练度✅✅✅✅
题目
给定一个整数数组 nums#xff0c;将数组中的元素向右轮转 k 个位置#xff0c;其中 k 是非负数。 示例 1: 输入: nums [1,2,…链接轮转数组题序号189题型数组解法1. 额外数组法2. 原数组翻转法三次翻转法难度中等熟练度✅✅✅✅
题目
给定一个整数数组 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 进阶 尽可能想出更多的解决方案至少有 三种 不同的方法可以解决这个问题。 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗
题解
额外数组法
核心要点遍历原数组将原数组下标为 i 的元素放至新数组下标为 (ik) mod n 的位置最后将新数组拷贝至原数组即可。复杂度时间复杂度O(n)空间复杂度O(n)。c 实现算法
class Solution {
public:void rotate(vectorint nums, int k) {int n nums.size();vector int newarr(n);for(int i 0; i n; i ) {newarr[(ik)%n] nums[i];}nums.assign(newarr.begin(), newarr.end()); }
};
算法推演 n7,k3 (03)%73 newarr[3] nums[0] 1 (13)%74 newarr[4] nums[1] 2 (23)%75 newarr[5] nums[2] 3 (33)%76 newarr[6] nums[3] 4 (43)%70 newarr[0] nums[4] 5 (53)%71 newarr[1] nums[5] 6 (63)%72 newarr[2] nums[6] 7 原数组翻转法三次翻转法
核心要点现将整个数组翻转再将前 k 个数翻转最后将剩下元素翻转。复杂度时间复杂度O(n)其中 n 为数组的长度。每个元素被翻转两次一共 n 个元素因此总时间复杂度为 O(2n)O(n)空间复杂度O(1)。c 实现算法翻转可以利用swap函数数组首尾交换实现。
class Solution2 {
public:void reverse(vectorint nums, int start, int end) {while (start end) {swap(nums[start], nums[end]);start 1;end - 1;}}void rotate(vectorint nums, int k) {k % nums.size(); //k3%73,为了旋转不超过数组长度reverse(nums, 0, nums.size() - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.size() - 1);}
};推演算法 推演: 输入数组1 2 3 4 5 6 7 第一次翻转7 6 5 4 3 2 1 第二次翻转5 6 7 4 3 2 1 第三次翻转5 6 7 1 2 3 4 c 完整demo
#include iostream
#include vectorusing namespace std;class Solution {
public:void rotate(vectorint nums, int k) {int n nums.size();vector int newarr(n);for(int i 0; i n; i ) {newarr[(ik)%n] nums[i];}nums.assign(newarr.begin(), newarr.end()); }
};
class Solution2 {
public:void reverse(vectorint nums, int start, int end) {while (start end) {swap(nums[start], nums[end]);start 1;end - 1;}}void rotate(vectorint nums, int k) {k % nums.size(); //k3%73,为了旋转不超过数组长度reverse(nums, 0, nums.size() - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.size() - 1);}
};
int main() {vector int nums {1, 2, 3, 4, 5, 6, 7};int k 3;//Solution solution;Solution2 solution;solution.rotate(nums, k);for(int i 0; i nums.size(); i) {cout nums[ i ]: nums[i] endl;}return 0;
}
