【数组】189. 旋转数组

[lyonyang]

给定一个数组，将数组中的元素向右移动 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]

提示：

1 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[zhangke666163]

思路：复制一个新数组，将旧数组元素右移K个位置，替换到新数组对应位置，注意移动时数组越界问题。
时间、空间复杂度：O(n)
代码：

import copy
def array_right(nums, k):
    k = k % len(nums)
    # k等于数组长度时，元素位置不会改变，输出原数组即可
    if k == 0:
        return nums
    new_array = copy.deepcopy(nums)
    for i in range(len(nums)):
        if i+k < len(nums):
            # 数组下标未越界
            new_array[i+k] = nums[i]
        else:
            # 数组下标越界
            new_array[i+k-len(nums)] = nums[i]
    return new_array

if __name__ == '__main__':
    print(array_right([1,2,3,4,5,6,7], 3))

[chuchumeme]

方法一：（通过了）

思路:

循环每一项，根据k值旋转放入新数组，再把新数组循环赋值给nums

复杂度

时间复杂度: 0(n) 空间复杂度: O(n)

代码:

const len = nums.length;
const arr = [];
for (let i = 0; i < len; i++) {
    arr[(i + k) % len] = nums[i];
}
for (let i = 0; i < len; i++) {
    nums[i] = arr[i];
}

方法二：（没过，超出时间限制）

思路:

通过while循环，将k减到0则旋转完成，数组进行弹出和插入

复杂度

时间复杂度: 0(n) 空间复杂度: O(n)

代码：

while(k > 0) {
  nums.unshift(nums.pop());
  k--;
}

为啥超出时间限制了。。

[xuezc1119]

方法一

思路

通过给定的k将数组分成两部分
将这两部分逆向拼接起来

复杂度

时间复杂度O(n)，空间复杂度O(n)

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
 var rotate = function(nums, k) {
  nums.push(...nums.splice(0, nums.length - k % nums.length)); // 删除前半段，取后半段,两者拼接
};

方法二

思路

通过k确定数组第一位到最后一位的新位置
剩余的数据前移

复杂度

时间复杂度O(n)，空间复杂度O(n)

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    let index = k % nums.length;
    console.log(index);
    if (index > 0) { // 等于0不移动
        let temp = JSON.parse(JSON.stringify(nums));
        for (let i = 0; i < index; i++) { // 前移数据
            nums[index - i - 1] = temp[temp.length - 1 - i]; // 倒着赋值
        }
        for (let i = index; i < nums.length; i++) { // 后移数据
            nums[i] = temp[i - index];
        }
    }
};

[lyonyang]

思路一 - 切片拼接

以倒数第 k 位置为分界线 , 用切片切分出两个数组 , 再拼接两个数组 , 由于要求在原地操作所以最后再进行一下复制 (但是这样的话空间复杂度为 $O(N)$ 而不是 $O(1)$)

注意 : k 可能大于数组长度

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums[:] = nums[len(nums) - k % len(nums):] + nums[:len(nums) - k % len(nums)]

时间复杂度：$O(N)$ , N 为数组长度

空间复杂度：$O(N)$

思路二 - 环形换位

向右移动 k 个位置 , 或者是向左移动 nums.length - k 个位置

向左换位 : 从尾部开始遍历 , 将第 i 个元素与第 i - nums.length - k 个元素互换 , 互换之前需要将被互换的位置的元素用变量存储起来再作为下一个换位的元素继续重复操作 , 整个换位过程刚好形成一个环

向右换位 : 从头部开始遍历 , 将第 i 个元素与第 i + k 个元素互换 , 互换之前同样需要将被互换的位置的元素用变量存储起来再作为下一个换位的元素继续重复操作 , 整个换位过程刚好形成一个环

注意 :

• k 可能大于数组长度
• k % len(nums) == 0 表示数组不移动
• 换位过程中可能有多个环 , 所以如果没有遍历完 , 当下一个索引回到了开始索引时 , 就应该往后挪一位继续换位操作

# 以右移为例
class Solution:
    def rotate(self, nums, k) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if k % len(nums) == 0: return
        start, index, next_num = 0, 0, nums[0]
        for i in range(len(nums)):
            next_index = (index + k) % len(nums)
            next_num, nums[next_index] = nums[next_index], next_num
            index = next_index
            if next_index == start:
                index = start = start + 1
                next_num = nums[index]

时间复杂度：$O(N)$ , N 为数组长度

空间复杂度：$O(1)$

思路三 - 三次反转

向右移 k 个位置 , 就是把从 len(nums) - k 到 len(nums) -1 的这段数组 , 与从 0 到 len(nums) - k - 1 这段数组调换一下位置 , 那我们可以 :

1. 先反转整个数组 , 使两段数组的位置正确
2. 但是由于反转了整个数组 , 所以两段数组的位置顺序都被反转了 , 那么我们再分别反转这两段数组

class Solution:
    def rotate(self, nums, k) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        self.reverse(0, len(nums) - 1, nums)
        self.reverse(0, k % len(nums) - 1, nums)
        self.reverse(k % len(nums), len(nums) - 1, nums)

    def reverse(self, start, end, nums):
        for i in range((end - start + 1) // 2):
            nums[start + i], nums[end - i] = nums[end - i], nums[start + i]

时间复杂度：$O(N)$ , N 为数组长度

空间复杂度：$O(1)$