跟LintCode的算法题杠上了（1334旋转数组）

本文主要是介绍跟LintCode的算法题杠上了（1334旋转数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定一个数组，将数组向右移动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)的时间复杂度解决问题吗?

思路

数组长度=1 直接返回
k=0直接返回
可以利用System.arraycopy数组复制
也可以利用遍历，交换位置

方法一


public static int[] rotate1(int[] nums, int k) {if(nums.length == 1 || k == 0){return nums;}//用临时数组来放移动后的数组int arr1 [] = new int[nums.length];if(k > nums.length){k = k % nums.length;}//先把需要移动K 步 的 数字添加到新数组的 头部System.arraycopy(nums,nums.length - k,arr1,0,k);//然后把剩下的数组放在新数组的后面System.arraycopy(nums,0,arr1,k,nums.length - k);return arr1;
}

方法二


public static int[] rotate(int[] nums, int k) {if(nums.length == 1 || k == 0){return nums;}//用临时数组来放移动后的数组int arr1 [] = new int[nums.length];if(k > nums.length){k = k % nums.length;}int index = 0;for(int i = 0; i < nums.length; i ++){if(i < (nums.length - k)){arr1[k + i] = nums[i];}else{arr1[index] = nums[i];index ++;}}return arr1;
}