189. Rotate Array

原题

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Could you do it in-place with O(1) extra space?

代码实现

空间复杂度O(1)，时间复杂度O(logn)

/// <summary> /// RotateArraySln /// </summary> public class RotateArraySln { public void Rotate(int[] nums, int k) { int n = nums.Length; if (n == 0 || n == 1) return; if ((double)k / n > 1) k = k % n; if (k == 0) return; Reverse(nums, 0, n - k); //index, length Reverse(nums, n - k, k); Reverse(nums, 0, n); } private void Reverse(int[] nums, int index, int length) { int i = 0; int loop = length/2; while (i < loop) { swap(ref nums[index + i], ref nums[length + index - i - 1]); i++; } } private void swap(ref int a, ref int b) { int tmp = a; a = b; b = tmp; } }

.NET简介版

public void Rotate(int[] nums, int k) { int n = nums.Length; if (n == 0 || n == 1) return; if ((double)k / n > 1) k = k % n; if (k == 0) return; System.Array.Reverse(nums, 0, n - k); //index, length System.Array.Reverse(nums, n - k, k); System.Array.Reverse(nums); }