原题链接:Leetcode 189. Rotate Array
Given an integer array nums
, rotate the array to the right by k
steps, where k
is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
- 1 <= nums.length <= 105
- -231 <= nums[i] <= 231 - 1
- 0 <= k <= 105
Follow up:
- Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
- Could you do it in-place with O(1) extra space?
题目大意:
给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置。
题目有多种解法。
方法一:使用额外数组
思路:
最先想到的笨办法,将元素移动到临时数组对应的位置,最后再将元素取回原数组
C++ 代码:
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> tmp(n);
for(int i = 0; i < n; i++ ){
tmp[(i + k) % n] = nums[i];
}
nums.assign(tmp.begin(), tmp.end());
}
};
复杂度分析:
- 时间复杂度:O(n),遍历了一遍数组
- 空间复杂度:O(n),用了一个和原数组等长的临时数组
补充:vector容器的assign():
函数原型:
void assign(const_iterator first,const_iterator last);
void assign(size_type n,const T& x = T());
功能:
- 将区间
[first,last)
的元素赋值到当前的vector容器中,或者n个值为x的元素到vector容器中,这个容器会清除掉vector容器中以前的内容。