旋转数组

发表于 | 分类于 |
字数统计: 1.1k 字 | 阅读时长 ≈ 4 分钟

题目描述：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

示例 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]

方法一：使用额外数组

用 n 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k) % n 的位置，最后将新数组拷贝至原数组即可。

1
2
3
4
5
6
7
8
9
10
class Solution {
    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);
    }
}

复杂度分析

  • 时间复杂度： O(n)，其中 n 为数组的长度。
  • 空间复杂度： O(n)。

执行结果：通过

  • 执行用时：2 ms, 在所有 Java 提交中击败了32.04%的用户

  • 内存消耗：55 MB, 在所有 Java 提交中击败了69.11%的用户

方法二：多次翻转

思路如下：

  1. 首先对整个数组实行翻转，这样子原数组中需要翻转的子数组，就会跑到数组最前面。
  2. 这时候，从 k 处分隔数组，左右两数组，各自进行翻转即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void rotate(int[] nums, int k) {
        int length = nums.length;
        // 当我们将数组的元素向右移动 k 次后，尾部 kmodn 个元素会移动至数组头部，其余元素向后移动 kmodn 个位置
        k %= nums.length;
        if(k == 0) return; 
        reverse(nums, 0, length - 1);//先反转全部的元素
        reverse(nums, 0, k - 1);//在反转前k个元素
        reverse(nums, k, length - 1);//接着反转剩余的
    }

    //把数组中从[start，end]之间的元素两两交换,也就是反转
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组的长度。每个元素被翻转两次，一共 n 个元素，因此总时间复杂度为 O(2n)=O(n)。

  • 空间复杂度：O(1)。

执行结果：通过

  • 执行用时：2 ms, 在所有 Java 提交中击败了32.04%的用户

  • 内存消耗：54.9 MB, 在所有 Java 提交中击败了75.05%的用户

方法三：环形旋转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 环形旋转
class Solution {
     public void rotate(int[] nums, int k) {
         int length = nums.length;
        // 当K等于数组长度时，如果直接移动的话，可能会让整个数组向右平移数组长度的位置，那其实还是原数组没变，所以大于数组长度的K可以直接取余找到多余的那一段需要平移的长度，再移动就可以了
        k %= length;
        if(k == 0) return; 
        int count = 0;  //移动总次数，总次数只需要
         //nums.leng为偶数时，会形成多个换环 1 2 3 4（1 3 1,2 4 2,3,1,3） ，为奇数时则只有一个环 1 2 3 4 5 （1 3 5 2 4 1），i=0不会增加
        for(int i = 0;count <length;i++){
            int current = i;//当前坐标
            int pre = nums[i];//前一个坐标
            do{
                int next = (current+k) % length;//下一个坐标
                //交换
                int temp = nums[next];
                nums[next] = pre;
                pre = temp;
                current = next;
                count++;
            }while(current != i );
        }
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组的长度。每个元素只会被遍历一次。
  • 空间复杂度：O(1)。我们只需常数空间存放若干变量。

执行结果：通过

  • 执行用时：2 ms, 在所有 Java 提交中击败了32.04%的用户

  • 内存消耗：55.3 MB, 在所有 Java 提交中击败了42.77%的用户