乐山做美食推荐的网站,wordpress ajax评论,网站设计参考网站,phpmysql旅游网站开发**给定一个数组#xff0c;将数组中的元素向右移动 k 个位置#xff0c;其中 k 是非负数。
进阶#xff1a; 尽可能想出更多的解决方案#xff0c;至少有三种不同的方法可以解决这个问题。 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗#xff1f;
示例 1: …**给定一个数组将数组中的元素向右移动 k 个位置其中 k 是非负数。
进阶 尽可能想出更多的解决方案至少有三种不同的方法可以解决这个问题。 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗
示例 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]**
方法一通过空间换取时间的方式在新的数据中排好在放入nums中我写的代码比较冗余刚开始没考虑到移动的步长会超过数组大小的情况
class Solution {
public:void rotate(vectorint nums, int k) {//空间换时间int temp[nums.size()],temp_numberk,sub_number;//不改变k的大小int i,j;sub_numbertemp_number/nums.size();temp_numberk-nums.size()*sub_number;int temp_number1temp_number;printf(%d\n,sub_number);for(i0;itemp_numbernums.size()1;i){temp[temp_number-i-1]nums[nums.size()-i-1];}for(j0;jnums.size()-temp_number1nums.size()1;j){temp[temp_number]nums[j];}for(i0;inums.size()nums.size()1nums.size()!k;i){nums[i]temp[i];}}
};改进版本
class Solution {
public:void rotate(vectorint nums, int k) {int i,nnums.size();int temp[n]; // 临时存储数据for(i0;in;i){temp[(ik)%n]nums[i]; }//数组复制for(i0;in;i){nums[i]temp[i];}}
};代码简化了一下也更好理解了优点先循环队列的思路
方法二
class Solution {
public:void reserve(vectorint nums,int begin,int end){int temp;while(beginend){ tempnums[begin];nums[begin]nums[end];nums[end]temp;begin;end--; }}void rotate(vectorint nums, int k) {k % nums.size();reserve(nums, 0, nums.size() - 1);reserve(nums, 0, k - 1);reserve(nums, k, nums.size() - 1);}};
