怎样制作一个网站步骤,优书网,跨境经验分享,网站流量监测“路虽远#xff0c;行则将至” ❤️主页#xff1a;小赛毛 ☕今日份刷题#xff1a;轮转数组 题目链接#xff1a;轮转数组 题目描述#xff1a; 给定一个整数数组 nums#xff0c;将数组中的元素向右轮转 k 个位置#xff0c;其中 k 是非负数。 示例1#xff1a; 输入… “路虽远行则将至” ❤️主页小赛毛 ☕今日份刷题轮转数组 题目链接轮转数组 题目描述 给定一个整数数组 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 如 [1,2,3,4,5,6,7]||
[7,6,5,4,3,2,1]
挪动一个数据
右旋一次
合计右旋k次 时间复杂度O(K*N) or O(N^2)空间复杂度O(1) 方法2 空间换时间 如 [1,2,3,4,5,6,7] k 3|| 直接把后k个copy过来)
[5,6,7]|| 再把前n-k个copy到后面)
[5,6,7,1,2,3,4] 时间复杂度O(N)空间复杂度O(N) 方法3: 如 [1,2,3,4,5,6,7] k 3|| 前n-k个逆置)
[4,3,2,1,5,6,7]|| 后k个逆置)
[4,3,2,1,7,6,5]|| 整体逆置)
[5,6,7,1,2,3,4] 时间复杂度O(N)空间复杂度O(1) 由于第三种方法可能没有那么容易思考到所以我们这里只简单操作一下第二种方法
代码
void rotate(int* nums, int numsSize, int k){int*tmp(int*)malloc(sizeof(int)*numsSize);int nnumsSize;k%n;memcpy(tmp,numsn-k,sizeof(int)*k);memcpy(tmpk,nums,sizeof(int)*(n-k));memcpy(nums,tmp,sizeof(int)*(n));free(tmp);
}
