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].Note:Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.[show hint]Hint:Could you do it in-place with O(1) extra space?空间复杂度O(1)
Hide Tags: Array
解题思路:
先将5以前的数据翻转得到的数组是[4,3,2,1,5,6,7]
再将5及以后的数据翻转得到的数组是[4,3,2,1,7,6,5]
再将整个数组翻转即得到[5,6,7,1,2,3,4].(即为所求)
代码如下:
public static void rotate(int[]nums,int k){//获取数组长度int size=nums.length;/** * 如果K>size,求其等效长度,起初会认为K<size,但是在leetcode的OJ测试的时候 * 会出现这种规律,,如实加了下面这行等效长度代码。 */if (k>size){k=k%size;}//翻转第K位(不包括第K位)之前的数reversal(nums,0,size-k-1);//翻转第k位(包括第K位)之后的数reversal(nums,size-k,size-1);//翻转整个数组reversal(nums,0,size-1);}public static void reversal(int[] nums,int i,int j){//设置中间存储变量int temp=0;//两端往中间依次进行换位while (i<j&&i>=0){temp=nums[j];nums[j]=nums[i];nums[i]=temp;i++;j–;}}
天不负;卧薪尝胆,三千越甲可吞吴。