Leetcode-189-旋转数组

Leetcode-189-Rotate Array

思路：遍历替换

题目描述

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

输入: [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]

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

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

方法一：暴力替换

最简单的方法是旋转 k 次，每次将数组旋转 1 个元素。

// 暴力解法
class Solution {
    public void rotate(int[] nums, int k) {
        int temp = 0;
        int previous = 0;

        // 外层循环：旋转k次
        for (int i = 0; i < k; i++) {
            previous = nums[nums.length - 1];
            // 内层循环：每次和数组中最后一个元素交换
            for (int j = 0; j < nums.length; j++) {
                temp = nums[j];
                nums[j] = previous;
                previous = temp;
            }
        }
    }
}

• 时间复杂度：O(n*k) 内层循环n个元素，外层循环遍历k次
• 空间复杂度：O(1)

方法二：使用额外的数组

• 思路：使用一个额外的数组把每个元素放到正确的位置上，也就是把i放到了 i + k%数组长度的位置。然后将数组重新拷贝到原数组中

class Solution {
    public void rotate(int[] nums, int k) {

        int[] a = new int[nums.length];
        
        // 新建一个数组，把对应位置存到新数组中
        for (int i = 0; i < nums.length; i++) {
            a[(i+k) % nums.length] = nums[i];
        }
        
        // 拷回到原数组中
        for (int i = 0; i < nums.length; i++) {
            nums[i] = a[i];
        }
    }
}

• 时间复杂度：O(n) 。将数字放到新的数组中需要一遍遍历，另一边来把新数组的元素拷贝回原数组。
• 空间复杂度：O(n)。另一个数组需要原数组长度的空间。

方法三 ： 数组翻转（建议使用）

• 该方法基于如下的事实：当我们将数组的元素向右移动 k 次后，尾部k mod n 个元素会移动至数组头部，其余元素向后移动 k mod n个位置。
• 该方法为数组的翻转：
  • 第一步 ：我们可以将所有的元素翻转，这样尾部的 k mod n 个元素就会移动到数组的头部
  • 第二步 ：翻转 0 到 (k mod n) - 1元素
  • 第三步 ：翻转 (k mod n) 到 n - 1元素

我们以 n=7，k=3 为例进行如下展示：

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums,0,nums.length - 1);            // 1. 翻转所有元素
        reverse(nums,0,k - 1);                      // 2. 翻转 0 到 (k mod n) - 1元素
        reverse(nums,k,nums.length - 1);            // 3. 翻转 (k mod n) 到 n - 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;
        }
    }
}

复杂度分析

• 时间复杂度 ： O(n)
• 空间复杂度 : O(1)

输入处理

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class MainClass {
    // 输入字符串数组转int数组
    public static int[] stringToIntegerArray(String input){
        input = input.trim();
        input = input.substring(1,input.length() - 1);
        if (input.length() == 0){
            return new int[0];
        }

        String[] parts = input.split(",");
        int[] output = new int[parts.length];
        for (int i = 0; i < parts.length; i++) {
            String part = parts[i].trim();
            output[i] = Integer.parseInt(part);
        }
        return output;
    }
	
    // 输出Int[]数组转字符串数组
    public static String integerArrayToString(int[] nums,int length){
        if (length == 0){
            return "[]";
        }
        String result = "";
        for (int i = 0; i < length; i++) {
            int number = nums[i];
            result += Integer.toString(number) + ", ";
        }
        return "[" + result.substring(0,result.length() - 2) + "]";
    }
	
    // 重载上述integerArrayToString方法
    public static String integerArrayToString(int[] nums){
        return integerArrayToString(nums,nums.length);
    }

    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine())!=null){
            int[] nums = stringToIntegerArray(line);
            line = in.readLine();
            int k = Integer.parseInt(line);

            new Solution().rotate(nums,k);
            String out = integerArrayToString(nums);
            System.out.println(out);
        }
    }
}

打赏