题目难度：中等
默认优化目标：最小化平均时间复杂度。
Python默认为Python3。
1 题目描述
给定一个整数数组 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]
提示：
-
1 <= nums.length <= 105 -
-231 <= nums[i] <= 231 - 1 -
0 <= k <= 105
进阶：
-
尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
-
你可以使用空间复杂度为
O(1)的 原地 算法解决这个问题吗？
2 题目解析
输入是一个整数数组nums，输出是元素向右轮转k个位置后的数组。
暴力求解就是另外开辟一个数组，把nums中的元素按照题目要求一个一个放进去。这显然去面试的人每个人应该都会，所以不推荐，没优势。另外一种就是循环指针，把数组的首尾连接起来，依次向右轮转。
3 算法原理及程序实现
3.1 暴力求解
我们新开辟一个数组temp，然后遍历nums，将nums中的元素轮转k个位置取出放入temp，最后再用temp更新nums。
平均时间复杂度O(n)，平均空间复杂度O(n)。
C++代码实现
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n=nums.size();
vector<int> temp(n);
for(int i=0;i<n;i++){
temp[(i+k)%n]=nums[i];//轮转
}
nums.assign(temp.begin(),temp.end());//将temp中的元素全部复制到nums
}
};Python代码实现
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
temp = [0] * n
for i in range(n):
temp[(i + k) % n] = nums[i]
nums[:] = temp
3.2 循环链表
我们将数组nums首尾相连，用一个指针指向原来尾的位置，向左移动k个位置后断开，就产生了新的头尾。这样新的数组就是所求的数组。但毕竟这是数组不是链表，没这么方便。将数组转换成列表，费时又费空间。
平均时间复杂度O(n)，平均空间复杂度O(n)。
C++代码实现
class Solution {
public:
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
void rotate(std::vector<int>& nums, int k) {
if (nums.empty() || k == 0) return;
// 将数组转换为链表
ListNode* head = new ListNode(nums[0]);
ListNode* current = head;
for (int i = 1; i < nums.size(); ++i) {
current->next = new ListNode(nums[i]);
current = current->next;
}
// 找到链表的尾部并连接成环
ListNode* tail = current;
tail->next = head;
// 找到新的尾部和头部
int stepsToNewHead = nums.size() - k % nums.size();
ListNode* newTail = tail;
for (int i = 0; i < stepsToNewHead; ++i) {
newTail = newTail->next;
}
ListNode* newHead = newTail->next;
// 断开环
newTail->next = nullptr;
// 将链表转换回数组
current = newHead;
for (int i = 0; i < nums.size(); ++i) {
nums[i] = current->val;
current = current->next;
}
// 释放链表内存
while (newHead) {
ListNode* temp = newHead;
newHead = newHead->next;
delete temp;
}
}
};
Python3代码实现
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
if not nums or k == 0:
return
# 将数组转换为链表
head = ListNode(nums[0])
current = head
for num in nums[1:]:
current.next = ListNode(num)
current = current.next
# 找到链表的尾部并连接成环
tail = current
tail.next = head
# 找到新的尾部和头部
steps_to_new_head = len(nums) - k % len(nums)
new_tail = tail
for _ in range(steps_to_new_head):
new_tail = new_tail.next
new_head = new_tail.next
# 断开环
new_tail.next = None
# 将链表转换回数组
current = new_head
for i in range(len(nums)):
nums[i] = current.val
current = current.next3.3 环状替代
要想空间复杂度为O(1)，我们不能使用额外的数组，也就是我们只能用一个零时变量temp来保存要被替代的元素。
替换规则为(i+k)%n，n为nums的长度。要保证每个元素都被替换，我们就要解决循环终止条件。假设我们走了a圈，遍历了b个元素，则有an=bk。an一定是n、k的公倍数。我们希望a越小越好，故an是n、k的最小公倍数lcm(n,k)。所以b=lcm(n,k)/k。所以我们需要遍历的次数为
gcd为最大公约数。
平均时间复杂度为O(n)，平均空间复杂度为O(1)。
C++代码实现
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;//防止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);
}
}
};Python代码实现
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k = k % n # 防止k超过n
count = gcd(k, n) # 确定循环次数
for start in range(count):
current = start
prev = nums[start] # 记录当前元素
while True: # 交换操作
next_idx = (current + k) % n
nums[next_idx], prev = prev, nums[next_idx]
current = next_idx
if start == current:
break3.4 数组翻转
该方法的原理：数组中的元素全部向右移动k位置，尾部k%n个元素会移到数组头部，其余元素会向后移动k%n个位置。
该方法步骤：①先将所有元素翻转②翻转[0,k%(n-1)]区间内的元素③翻转[k%n,n-1]区间内的元素。
第一步让尾部元素到头部，第二部让新的头部元素顺序正确，第三步让新的尾部元素顺序正确。
示例如下，n=7，k=3。
| 操作 | 结果 |
|---|---|
| nums | [1,2,3,4,5,6,7] |
| 步骤① | [7,6,5,4,3,2,1] |
| 步骤② | [5,6,7,4,3,2,1] |
| 步骤③ | [5,6,7,1,2,3,4] |
平均时间复杂度为O(n)，平均空间复杂度为O(1)。
C++代码实现
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n=nums.size();
k%=n;
reverse(nums.begin(),nums.end());
reverse(nums.begin(),nums.begin()+k);
reverse(nums.begin()+k%n,nums.end());
}
};Python代码实现
class Solution:
def rotate(self, nums, k):
n = len(nums)
k %= n
nums.reverse()
nums[:k] = reversed(nums[:k])
nums[k:] = reversed(nums[k:])4 题目难度
这道题难在用O(1)的空间复杂度完成。相比于环状替代，数组翻转方法既好理解效果又好。