来源：力扣（LeetCode）
链接: https://leetcode.cn/problems/rotate-array/
给你一个数组，将数组中的元素向右轮转 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 <= nums.length <= 10^5
−
2
31
-2^{31}
−231 <= nums[i] <=
2
31
−
1
2^{31} - 1
231−1
0 <= k <=
1
0
5
10^5
105
- 新数组保存反转后的元素，再赋值给原先数组：使用新的存储空间存储原有数组变换后的元素，之后再赋值给原始数组
- 本地反转： 先整体反转，然后反转前k个，再反转后n-k个；
nums = "----->-->"; k =3 result = "-->----->"; reverse "----->-->" we can get "<--<-----" reverse "<--" we can get "--><-----" reverse "<-----" we can get "-->----->" this visualization help me figure it out :)
- 环状替换：第一种方法需要使用一个数组来保存，这里用一个变量来保存要替换的元素，替换之后再保存这个要替换的元素，更新新的index，一直这样下去，直到回答初始位置之后，以邻近的下一个元素为新的开始，整个环状替换次数为gcd(k, n), 其中k也是%n后的值
python实现
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
auxArr = [0] * len(nums)
k %= len(nums)
for i in range(len(nums)):
auxArr[(i + k) % len(nums)] = nums[i]
nums[:] = auxArr
c++实现
class Solution {
public:
void rotate(vector& nums, int k) {
int n = nums.size();
vector newNums(n);
for (int i=0; i
newNums[(i+k)%n] = nums[i];
}
nums.assign(newNums.begin(), newNums.end());
}
};
复杂度分析
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
python实现
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k %= n
nums[:] = nums[::-1]
nums[:k] = nums[:k][::-1]
nums[k:] = nums[k:][::-1]
c++实现
class Solution {
public:
void reverse(vector& nums, int start, int end) {
while (start < end) {
swap(nums[start], nums[end]);
start++;
end--;
}
}
void rotate(vector& nums, int k) {
int n = nums.size();
k %= n;
reverse(nums, 0, n-1);
reverse(nums, 0, k-1);
reverse(nums, k, n-1);
}
};
复杂度分析
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( 1 ) O(1) O(1)
python实现
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k %= n
count = self.gcd(n, k)
for start in range(count):
current = start
prev = nums[current]
while True: # do while
nextIndex = (current+k) % n
prev, nums[nextIndex] = nums[nextIndex], prev
current = nextIndex
if current == start:
break
def gcd(self, a, b):
if b == 0:
return a
return self.gcd(b, a%b)
c++实现
class Solution {
public:
void rotate(vector& nums, int k) {
int n = nums.size();
k = k % n;
int count = gcd(k ,n);
for(int start=0; start < count; start++) {
int current = start;
int prev = nums[start];
do {
int next = (current+k) % n;
swap(nums[next], prev);
current = next;
} while (start != current);
}
}
};
复杂度分析
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( 1 ) O(1) O(1)
- https://leetcode.cn/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/
- https://segmentfault.com/a/1190000038163495
- https://codeantenna.com/a/wyZwqVYDiJ
- https://www.delftstack.com/zh/howto/python/python-do-while/
