题解 | #旋转数组#
旋转数组
http://www.nowcoder.com/practice/e19927a8fd5d477794dac67096862042
一、模拟
时间(N) 空间(N)
算法:当前i为i-m的数,m可能大于n所以m=m%n
import java.util.*;
public class Solution {
public int[] solve (int n, int m, int[] a) {
// write code here
int[] ans=new int[n];
m=m%n;
for(int i=0;i<n;i++){
ans[i]=a[(i-m+n)%n];
}
return ans;
}
}
二、对称法
时间(N) 空间(1)
算法:先全部对称,再0到n-1对称,再0到m-1对称再m到n-1对称
import java.util.*;
public class Solution {
public int[] swap(int i, int j, int[] a){
while(i<j){
int t = a[i];
a[i++]=a[j];
a[j--]=t;
}
return a;
}
public int[] solve (int n, int m, int[] a) {
// write code here
m=m%n;
swap(0,n-1,a);
swap(0,m-1,a);
swap(m,n-1,a);
return a;
}
}