定州市住房和建设局网站,北京代理记账财务公司,上海网站建设 润,网站建站授权模板下载前言#xff1a;内容包括#xff1a;题目#xff0c;代码实现#xff0c;大致思路#xff0c;代码解读
题目#xff1a;
给定一个整数数组 nums#xff0c;将数组中的元素向右轮转 k 个位置#xff0c;其中 k 是非负数。 示例 1:
输入: nums [1,2,3,4,5,6,7], k 3…前言内容包括题目代码实现大致思路代码解读
题目
给定一个整数数组 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]
代码实现
void Reverse(int *nums,int left,int right)
{while(leftright){int tmp nums[left];nums[left]nums[right];nums[right]tmp;left;right--;}
}void rotate(int* nums, int numsSize, int k)
{if(knumsSize){kk%numsSize;}Reverse(nums,numsSize-k,numsSize-1);Reverse(nums,0,numsSize-k-1);Reverse(nums,0,numsSize-1);
}
大致思路
1 后部分逆置区间[n-k,n-1] 这里的n是数组的个数
2 前部分逆置区间[0,n-k-1]
3 整体逆置 区间[0.n-1]
如1,2,3,4,5,6,7k3
后部分逆置5~7因为5的下标是n-k7-347的下标是n-17-16
1 2 3 4 7 6 5
前部分逆置1~4因为1的下标是04的下标是n-k-17-3-13
4 3 2 1 7 6 5
整体逆置4~5
5 6 7 1 2 3 4
4 重点注意轮转的k可能比整个数组的个数大比如k13而数组的个数n7 这种情况下 则实际上轮转的kk%n。即k13%76 因为数组个数是7轮转7次原封不动还是原来的样子 那么我们真正有轮转效果的是剩下的6次13-7
代码解读
part 1 void rotate(int* nums, int numsSize, int k)
{if(knumsSize){kk%numsSize;}Reverse(nums,numsSize-k,numsSize-1);Reverse(nums,0,numsSize-k-1);Reverse(nums,0,numsSize-1);
}
1 判断轮转次数k是否比数组个数大若大于则实际的轮转次数kk%数组个数
单独写一个Reverse函数实现某个区间的数字逆置
2 后部分逆置
3 前部分逆置
4 整体逆置
part 2
void Reverse(int *nums,int left,int right)
{while(leftright){int tmp nums[left];nums[left]nums[right];nums[right]tmp;left;right--;}
}Reverse函数实现某个区间内数字的逆置
left是某个区间最左端数字的下标
right是某个区间最右端数字的下标
