题目链接

轮转数组

题目描述

注意点

• 使用空间复杂度为 O(1) 的 原地 算法解决这个问题

解答思路

• 本题有多种思路，一种是复制nums数组，然后将k个位置后的值赋值给当前位置即可，但是空间复杂度为O(n)
• 还有一种思路是先将整个数组进行翻转，再将(0, k - 1)和(k, n)之间的数组各自进行翻转，最后得到的数组就是结果

代码

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }
}

关键点

• 先将整个数组进行翻转，将后面k个数字移动前方，前面n - k个数字移到后方，再将这两部分分别进行翻转，保证顺序不变