Skip to content

Latest commit

 

History

History
218 lines (171 loc) · 5.57 KB

0189.旋转数组.md

File metadata and controls

218 lines (171 loc) · 5.57 KB

参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!

189. 旋转数组

力扣题目链接

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

思路

这道题目在字符串里其实很常见,我把字符串反转相关的题目列一下:

本题其实和字符串:剑指Offer58-II.左旋转字符串就非常像了,剑指offer上左旋转,本题是右旋转。

注意题目要求是要求使用空间复杂度为 O(1) 的 原地 算法

那么我来提供一种旋转的方式哈。

字符串:剑指Offer58-II.左旋转字符串中,我们提到,如下步骤就可以坐旋转字符串:

  1. 反转区间为前n的子串
  2. 反转区间为n到末尾的子串
  3. 反转整个字符串

本题是右旋转,其实就是反转的顺序改动一下,优先反转整个字符串,步骤如下:

  1. 反转整个字符串
  2. 反转区间为前k的子串
  3. 反转区间为k到末尾的子串

需要注意的是,本题还有一个小陷阱,题目输入中,如果k大于nums.size了应该怎么办?

举个例子,比较容易想,

例如,1,2,3,4,5,6,7 如果右移动15次的话,是 7 1 2 3 4 5 6 。

所以其实就是右移 k % nums.size() 次,即:15 % 7 = 1

C++代码如下:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());

    }
};

其他语言版本

Java

class Solution {
    private void reverse(int[] nums, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            int temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
        }
    }
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
}

Python

方法一:局部翻转 + 整体翻转

class Solution:
    def rotate(self, A: List[int], k: int) -> None:
        def reverse(i, j):
            while i < j:
                A[i], A[j] = A[j], A[i]
                i += 1
                j -= 1
        n = len(A)
        k %= n
        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

方法二:利用余数

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        copy = nums[:]

        for i in range(len(nums)):
            nums[(i + k) % len(nums)] = copy[i]
        
        return nums

        # 备注:这个方法会导致空间复杂度变成 O(n) 因为我们要创建一个 copy 数组。但是不失为一种思路。

Go

func rotate(nums []int, k int)  {
    l:=len(nums)
    index:=l-k%l
    reverse(nums)
    reverse(nums[:l-index])
    reverse(nums[l-index:])
}
func reverse(nums []int){
    l:=len(nums)
    for i:=0;i<l/2;i++{
        nums[i],nums[l-1-i]=nums[l-1-i],nums[i]
    }
}

JavaScript

var rotate = function (nums, k) {
  function reverse(nums, i, j) {
    while (i < j) {
      [nums[i],nums[j]] = [nums[j],nums[i]]; // 解构赋值
      i++;
      j--;
    }
  }
  let n = nums.length;
  k %= n;
  if (k) {
    reverse(nums, 0, n - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, n - 1);
  }
};

TypeScript

function rotate(nums: number[], k: number): void {
    const length: number = nums.length;
    k %= length;
    reverseByRange(nums, 0, length - 1);
    reverseByRange(nums, 0, k - 1);
    reverseByRange(nums, k, length - 1);
};
function reverseByRange(nums: number[], left: number, right: number): void {
    while (left < right) {
        const temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++;
        right--;
    }
}

Rust

impl Solution {
    pub fn rotate(nums: &mut Vec<i32>, k: i32) {
        let k = k as usize % nums.len();
        nums.reverse();
        nums[..k].reverse();
        nums[k..].reverse();
    }
}