【LeetCode热题100】【普通数组】轮转数组

本文主要是介绍【LeetCode热题100】【普通数组】轮转数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：189. 轮转数组 - 力扣（LeetCode）

用额外数组的话，时间和空间复杂度都是O(n)

不用二维数组直接循环移动k×n次暴力会超时，时间复杂度达到了O(kn)

考虑轮转的结果，向右移动k个位置的结果相对于整体翻转一次，然后0到k-1翻转一次，k到n-翻转一次的结果，向左移动的话则是k=n-k即可，让k=k%n去掉无效移动，这样每个元素被移动2次，时间复杂度为O(n)

class Solution {
public:void rotate(vector<int> &nums, int k) {auto reverse = [](vector<int> &nums, int begin, int end) -> void {while (begin < end) {swap(nums[begin++], nums[end--]);}};k = k % nums.size();reverse(nums, 0, nums.size() - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.size() - 1);}
};

这篇关于【LeetCode热题100】【普通数组】轮转数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---