
问题
给定一个数组,将数组中的元素向右移动 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的时间复杂度均为: ,Rotate的空间复杂度为:
,Rotate2的空间复杂度为:
。Rotate3的时间和空间复杂度基于运行时所使用的反转算法。
Rotate2的解法符合题目“原地打转”要求。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3700。