将数组后k个元素放到前面
注意:当k的值比n的值大的时候,是按照如下规律
【1,2,3】k=5
3-5=-2,从右往左两位等同于k=2
【2,3,1】
- java
1)使用reverse的思想:
【1,2,3,4,5,6,7】,k=2
先反转【7,6,5,4,3,2,1】
前k位反转 【6,7,5,4,3,2,1】
后面n-k位反转【6,7,1,2,3,4,5】
class Solution {
public void rotate(int[] nums, int k) {
if(nums==null||nums.length==0||k<=0)
return;
int n=nums.length;
List<Integer> list=new ArrayList<>();
//当k比n大的时候,比如【1,2,3】k=5,5%3=2,等同于k=2【2,3,1】
if(k>n){
k=k%n;
}
//将数组中所有元素反转
reverse(nums,0,n-1);
//将前k项反转
reverse(nums,0,k-1);
//将后面元素反转
reverse(nums,k,n-1);
}
public void reverse(int []nums,int start,int end){
for(;start<end;start++,end--){
int temp=nums[start];
nums[start]=nums[end];
nums[end]=temp;
}
}
}
2)用多余数组实现:
class Solution {
public void rotate(int[] nums, int k) {
if(nums==null||nums.length==0||k<=0)
return;
int n=nums.length;
int[] temp=new int[n];
//当k比n大的时候,比如【1,2,3】k=5,3-5=-2,等同于k=2【2,3,1】
if(k>n){
k=k%n;
}
for(int i=n-k,j=0;i<n&&j<k;i++,j++){
temp[j]=nums[i];
}
for(int i=0,j=k;i<n-k&&j<n;i++,j++){
temp[j]=nums[i];
}
for(int i=0;i<n;i++){
nums[i]=temp[i];
}
}
}
3)用多余list实现:
class Solution {
public void rotate(int[] nums, int k) {
if(nums==null||nums.length==0||k<=0)
return;
int n=nums.length;
List<Integer> list=new ArrayList<>();
//当k比n大的时候,比如【1,2,3】k=5,3-5=-2,等同于k=2【2,3,1】
if(k>n){
k=k%n;
}
for(int i=n-k;i<n;i++){
list.add(nums[i]);
}
for(int i=0;i<n-k;i++){
list.add(nums[i]);
}
for(int i=0;i<n;i++){
nums[i]=list.get(i);
}
}
}
- javascript
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function(nums, k) {
if(nums==null||nums.length==0||k<=0)
return;
var n=nums.length;
var list=new Array();
//当k比n大的时候,比如【1,2,3】k=5,3-5=-2,等同于k=2【2,3,1】
if(k>n){
k=k%n;
}
for(var i=n-k;i<n;i++){
list.push(nums[i]);
}
for(var i=0;i<n-k;i++){
list.push(nums[i]);
}
for(var i=0;i<n;i++){
nums[i]=list[i];
}
};