[数据结构与算法]【C++】vector实现数组内部元素顺序移动

题目

解题思路

思路1

1. 利用STL容器，在数组中的首元素前添加元素，其元素值为数组中最后一个元素的值
2. 删除数组中最后一个元素的值
3. 重复上述1,2步，实现k次移动
   
   

思路2

1. 创建新数组v并拷贝原数组nums数组
2. 判断循环次数
3. 将新数组+移动步数后所得的新值写回原数组nums

思路比较

• 思路1：相比于思路2，较为清晰，易于理解
• 思路2：在时间复杂度和空间复杂度都相对优于思路1
  
  

附加提示

• 在做循环移动时，循环次数不一定是k，应为k%size()
  ps：考虑到移动步数超过数组长度的情况，eg.长度为7，移动步数为10相当于移动了3步
• 访问首元素v.begin();
• 访问末元素v.end();
• 向位置pos插入elem元素insert(const_iterator pos, elem);
• 返回元素个数v.size();
• 删除最后一个元素pop_back();
  
  

代码实现

实现1

vector<int> rotate(vector<int> &nums, int k) {
    // Write your code here
    k%=nums.size();
    for(int i=0;i<k; i++)
    {
        nums.insert(nums.begin(),nums[nums.size()-1]);	//在首元素前添加元素，并将值赋为末元素的值
        nums.pop_back();	//删除末元素
    }
    return nums;
}

实现2

vector<int> rotate(vector<int> &nums, int k) {
    // Write your code here
    vector<int> v;
    for(int i=0;i<nums.size();i++)
    {
        v.push_back(nums[i]);	//创建新数组v并将nums的值全部拷贝
    }
    if(k>nums.size())     k%=nums.size();	//判断应循环的次数
    for(int i=0;i<nums.size();i++)	//将v中元素+移动步数的元素复制到nums数组中
    {
        nums[i]=v[(i-k+nums.size())%nums.size()];
    }
    return nums;
}