轮转数组 的题解

题目详情

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

1
2
3
4
5
6
输入: 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:

1
2
3
4
5
输入：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) 的 原地 算法解决这个问题吗？

首先暴力求解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void rotateA(int[] nums, int k) {
    for (int i = 0; i < k; i++) {
        reverse(nums);
    }
}

private static void reverse(int[] nums) {
    int temp = nums[nums.length - 1];
    // 从后往前遍历
    for (int i = nums.length - 1; i > 0; i--) {
        // 将当前元素的前一个元素赋值给当前元素
        nums[i] = nums[i - 1];
    }
    // 将最后一个元素赋值给第一个元素
    nums[0] = temp;
}

此解法的时间复杂度为O(n^2),当nums的length和k值过大时，会超时

image-20231212222417094

数组copy法

1
2
3
4
5
6
7
8
public void rotate(int[] nums, int k) {
    int n = nums.length;
    int[] newArr = new int[n];
    for (int i = 0; i < n; ++i) {
        newArr[(i + k) % n] = nums[i];
    }
    System.arraycopy(newArr, 0, nums, 0, n);
}

用空间换时间，其中需要注意的一点时 (i + k) % n

假定 nums = [1,2,3,4,5] k =2

第一次执行for循环的时候，我们会将 (i+k)%n => (0+2)%5

所以，我们会将1=> 放到 newArr[0] 的位置，so，数组为 [0,0,1,0,0]

经过 nums.length次转换，就会变成 => [4,5,1,2,3]

image-20231212223349501

数组翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void rotate(int[] nums, int k) {
    k %= nums.length; // 2
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}

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

解析 假定 nums = [1,2,3,4,5] k =2

首先，我们将数组进行反转 nums => [5,4,3,2,1]

其次，我们将0，k-1位置的数据进行反转 => [4,5,3,2,1]

最后，我们将k，nums.length上的数据进行反转 => [4,5,1,2,3]

环状替换 推荐好好理解理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        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;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    public int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }
/*
作者：力扣官方题解
链接：https://leetcode.cn/problems/rotate-array/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/