轮转数组（NB方法）

100 阅读 0 评论 66 点赞

我是靠谱客的博主失眠羊，这篇文章主要介绍轮转数组（NB方法），现在分享给大家，希望可以做个参考。

地址：189. 轮转数组 - 力扣（LeetCode） (leetcode-cn.com)

要求：空间复杂度为O(1)

有第一个实例知：

反转后的数组：(0-(k%n-1)) 反转 + （（k%n）- (n-1)）反转后等于原数组反转

故解决方法为：

先把原数组进行反转，然后(0-(k%n-1)) 反转 + （（k%n）- (n-1)）反转

class Solution {
public:
    void rotate(vector<int>& nums, int k) {

        int n = nums.size();
        reverse(nums,0,n-1);
        reverse(nums,0,k%n - 1);
        reverse(nums,k%n , n-1);
    }

    void reverse(vector<int> & nums , int start ,int end){
        while (start < end){
            swap(nums[start] , nums[end]);
            end--;
            start++;
        }
    }
};