189. 轮转数组(中等)

Posted on In Views:

1，问题描述

189. 轮转数组

难度：中等

给定一个整数数组 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) 的 原地 算法解决这个问题吗？

2，初步思考

​ 首先暴力遍历破解是可以解题的，本质就是全局去挨个相加测试结果是否等于target，但是算法时间复杂度为O(n^2)

​ 进阶要求时间复杂度小于O(n^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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
public class _189轮转数组 {

    // 解法6:递归处理，本质就是环状替代的变形
    // 其内部其实使用了存储空间，你可以想象一个虚拟的数组temp列表在外部缓存等待归位
    public void rotate_recursion(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        int count = gcd(k, n);
        for (int i = 0; i < count; i++) {
            swapNext(nums, k, nums[i], i, (i + k) % nums.length);
        }
    }

    private void swapNext(int[] nums, int k, int temp, int referenceIndex, int indexNext) {
        int indexNow = indexNext;
        indexNext = (indexNext + k) % nums.length;
        if (indexNow != referenceIndex) {
            swapNext(nums, k, nums[indexNow], referenceIndex, indexNext);
        }
        nums[indexNow] = temp;
    }

    // 解法5:环状替换(这个我当时有点思路，想使用递归处理)
    public void rotate_ring(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        int count = gcd(k, n);
        for (int i = 0; i < count; i++) {
            int current = i;
            int prev = nums[i];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (i != current);
        }
    }

    public int gcd(int a, int b) {// 最大公约数
        return b == 0 ? a : gcd(b, a % b);
    }

    // 解法4:反转法,时间复杂度O(n)、空间复杂度O(1)
    public void rotate_reverse(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, nums.length - k, nums.length - 1);
        reverse(nums, 0, nums.length - k - 1);
        reverse(nums, 0, nums.length - 1);
    }

    public void reverse(int[] arr, int l, int r) {
        if (arr == null || arr.length <= 1) return;
        while (l < r) {
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            l++;
            r--;
        }
    }


    // 解法3:双指针（暴力破解的优化版本），时间复杂度O(k+k*n)、空间复杂度O(1)
    public void rotate_duble_index(int[] nums, int k) {
        k = k % nums.length;
        if (k == 0) {
            return;
        }
        int start = 0;
        int counter = 0;
        if (k <= nums.length / 2) {
            // 短于一半
            start = k;
            counter = nums.length - 2 * k;
            for (int i = 0; i < start; i++) {
                swap(nums, i, nums.length - k + i);
            }
        } else {
            // k长于一半
            start = nums.length - k;
            counter = start;
            for (int i = 0; i < start; i++) {
                swap(nums, i, start + i);
            }
        }
        for (int i = 0; i < counter; i++) {
            for (int j = start; j < nums.length - 1; j++) {
                swap(nums, j, j + 1);
            }
        }
    }

    // 解法2:空间换时间，截取&拼接，时间复杂度O(n)、空间复杂度O(n)
  	// 可以参考官方的进行优化，直接无视边界
    public void rotate_area(int[] nums, int k) {
        k = k % nums.length;
        int[] temp = new int[nums.length];
        for (int i = 0; i < k; i++) {
            temp[i] = nums[nums.length - k + i];
        }
        for (int i = 0; i < nums.length - k; i++) {
            temp[i + k] = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = temp[i];
        }
    }


    // 解法1:本质暴力破解：直接进行交换，遍历k次即可 时间复杂度O(n*k)，运行超时
    public void rotate_iterate(int[] nums, int k) {
        k = k % nums.length;
        for (int i = 0; i < k; i++) {
            System.out.println();
            for (int j = nums.length - 1; j > 0; j--) {
                swap(nums, j, j - 1);
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        _189轮转数组 rotateArray = new _189轮转数组();
        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7};
//        int[] nums = new int[]{1,2,3};
//        rotateArray.rotate_ring(nums, 3);
        rotateArray.rotate_recursion(nums, 3);
        for (int num : nums) {
            System.out.println(num + " ");
        }

    }
}

/**
 * 1,2,3,4,5,6 , 7,8,9,10:k=4
 * 7,8,9,10 , 5,6 , 1,2,3,4
 * 7,8,9,10 , 6 , 1,2,3,4,5
 * 7,8,9,10 , 1,2,3,4,5,6
 * <p>
 * 7,8,9,10 , 1,2,3,4,5,6
 * <p>
 * <p>
 * [1,2,3,4,5,6]:k=1
 * [6 , 2,3,4,5 , 1]
 * <p>
 * [1,2,3,4,5,6,7,8]:k=6
 * [1,2 , 3,4,5,6,7,8]
 * [3,4, , 1,2 , 5,6,7,8]swap=>= len-k,index=len-k
 * 3,4,5,6,7,8 , 1,2
 * <p>
 * [1,2,3,4,5,6,7,8]:k=3
 * [1,2,3,4,5 , 6,7,8]
 * [6,7,8 , 1,2,3,4,5]swap=>= len-2k,index=k
 * <p>
 * [4,5,6,7,8, 1,2,3]
 * <p>
 * 解法4:反转法
 * [1,2,3,4,5,6,7,8]:k=3
 * [6,7,8,1,2,3,4,5]
 * <p>
 * [5,4,3,2,1 , 8,7,6]
 * <p>
 * <p>
 * <p>
 * nums[i] = nums[i-k];
 */

​ 下面是我思考之后的另一个解答，时间复杂度O(n)，空间复杂度O(n)

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
  	// 官方解法1:使用额外的数组进行缓存，时间复杂度O(n),空间复杂度O(n)
    public void rotate_gov_arr(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);
    }
  
  	// 官方解法2:环状替换，循环处理，时间复杂度O(n)，空间复杂度O(1)
    public void rotate_gov_ring(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;
    }
  
  	// 官方解法3:数组翻转，本质就是三次反转，时间复杂度O（n），空间复杂度O(1)
    public void rotate_reverse(int[] nums, int k) {
        k %= nums.length;
        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;
        }
    }
}

4，思考过程

​ 讲道理还是有点“困难”，翻转法很简单，但是我又没想到，想到的空间换时间又不满足空间复杂度要求！

​ 鉴定为“菜”，还得练！