C#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) 的原地算法。

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

Input: [1,2,3,4,5,6,7] and 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]

Input: [-1,-100,3,99] and 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]

Note:

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?

示例

public class Program {

    public static void Main(string[] args) {

        int[] nums = null;

        //[1,2,3,4,5,6,7] k = 3

        //第1次，反转尾部，1,2,3,4,7,6,5

        //第2次，反转头部，4,3,2,1,7,6,5

        //第3次，反转所有，5,6,7,1,2,3,4

        nums = new int[] { 1, 2, 3, 4, 5, 6, 7 };

        Rotate(nums, 3);

        ShowArray(nums);

        nums = new int[] { 1, 2, 3, 4, 5, 6, 7 };

        Rotate2(nums, 3);

        ShowArray(nums);

        nums = new int[] { 1, 2, 3, 4, 5, 6, 7 };

        Rotate3(nums, 3);

        ShowArray(nums);

        Console.ReadKey();

    }

    private static void ShowArray(int[] array) {

        foreach(var num in array) {

            Console.Write($"{num} ");

        }

        Console.WriteLine();

    }

    private static void Rotate(int[] nums, int k) {

        int[] newNums = new int[k];

        int length = nums.Length;

        k %= length;

        int mid = length - k;

        for(int i = 0; i < k; i++) {

            newNums[i] = nums[mid + i];

        }

        for(int i = mid - 1; i >= 0; i--) {

            nums[i + k] = nums[i];

        }

        for(int i = 0; i < k; i++) {

            nums[i] = newNums[i];

        }

    }

    private static void Reverse(int[] array, int index, int length) {

        for(int i = index, count = -1; i < index + length / 2; i++) {

            count++;

            int t = array[i];

            array[i] = array[index + length - count - 1];

            array[index + length - count - 1] = t;

        }

    }

    private static void Rotate2(int[] nums, int k) {

        if(nums.Length == 1 || k == 0) {

            return;

        }

        k %= nums.Length;

        Reverse(nums, nums.Length - k, k);

        Reverse(nums, 0, nums.Length - k);

        Reverse(nums, 0, nums.Length);

    }

    private static void Rotate3(int[] nums, int k) {

        if(nums.Length == 1 || k == 0) {

            return;

        }

        k %= nums.Length;

        Array.Reverse(nums, nums.Length - k, k);

        Array.Reverse(nums, 0, nums.Length - k);

        Array.Reverse(nums);

    }

}

以上给出3种算法实现，以下是这个案例的输出结果：

5 6 7 1 2 3 4

5 6 7 1 2 3 4

5 6 7 1 2 3 4

分析：

显而易见，Rotate和Rotate2的时间复杂度均为： $O(n)$ ，Rotate的空间复杂度为： $O(n)$ ，Rotate2的空间复杂度为： $O(1)$ 。Rotate3的时间和空间复杂度基于运行时所使用的反转算法。

Rotate2的解法符合题目“原地打转”要求。

巴特西

C#LeetCode刷题之#189-旋转数组（Rotate Array）

最新文章

热门文章