Leetcode经典面试Java算法189旋转数组

Given an array, rotate the array to the right by k steps, where k is non-negative.

Follow up:

• Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

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

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

解题思路：

首先这是一道难度值为简单的题型，注意题目要求最好空间复杂度O(1)，即不能定义额外数组，只能在参数数组中修改。

第一种解法比较直观：

根据k来循环嵌套移动数组，时间复杂度为KN

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        for (int i=0; i<k; i++) { //遍历k遍
            int last = nums[n-1]; // 保留数组的最后一位
            for (int j=n-1; j>=1; j--) { //逆序遍历，除了第一位，将剩余所有数组元素右移
                nums[j] = nums[j-1];
            }
            nums[0] = last; // 将最后一个元素放置第一个位置
        }
    }
}

第二种解法：

首先考虑如何保证时间复杂度为N？开脑洞。

原始数组: 1 2 3 4 5 6 7
将原始数组反转: 7 6 5 4 3 2 1
将前K个元素反转 : 5 6 7 4 3 2 1
将第N-K个元素反转 : 5 6 7 1 2 3 4

class Solution {
  public void rotate(int[] nums, int k) {
    k %= nums.length; //为什么要做求余操作？ 因为如果k > length，就会出现重复移位，所以求余避免重复移位
    reverse(nums, 0, nums.length - 1); //将原始数组反转
    reverse(nums, 0, k - 1); //将前K个元素反转
    reverse(nums, k, nums.length - 1); //将第N-K个元素反转
  }
  public void reverse(int[] nums, int start, int end) {
    while (start < end) {
      int temp = nums[start];
      nums[start] = nums[end];
      nums[end] = temp;
      start++;
      end--;
    }
  }
}