因为有些特殊情况,会陷入循环,比如这个例子:
我不知道怎么处理这种情况,所以直接搞个标记数组falgs[]来看看这个位置的数字是否被处理过。方法二来改进这个陷入循环的问题
class Solution {
public void rotate(int[] nums, int k) {
// 1.跳序 轮转法——带标记,时间复杂度和空间复杂度均为O(n)
int len=nums.length;
int[] flags=new int[len];
Arrays.fill(flags,0);
int next;
int curr=0;
int tmp=nums[curr]; //临时保存上一个
int tmp1; //临时保存当前的
int n=len;
while(n!=0 && k!=0){
// if(n!=len && len%k==0 &&n%(len/k)==0){
// curr++;
// tmp=nums[curr];
// }
next=(curr+k)%len;
while(flags[next]==1){
next=(next+1)%len;
if(flags[next]==1)
continue;
else {
curr=next;
tmp = nums[curr];
next = (curr + k) % len;
}
}
tmp1=nums[next];
nums[next]=tmp;
tmp=tmp1;
curr=next;
flags[curr]=1;
n--;
}
}
}
方法2:类1-跳序轮转法——不借助flag数组
这里稍微对pos==i解释一下,因为pos如果一次陷入循环,意味着pos会在不同的轮转中循环,即跳出一个轮回会进入下一个轮换,在每个轮回中都会陷入循环。pos是从0开始,那当pos跳转一轮回到起点0以后,就派i(可以看做pos的初始)对线,发现跟初始0一样,就开始对pos+1处理。
(我们把这样叫一次轮转,从pos=0出发,回到pos=0)
class Solution {
public void rotate(int[] nums, int k) {
// 5.类1-跳转轮转法:他人解法,不借助flag数组
int len = nums.length,n = len;
int i = 0,pos = 0, pre = nums[pos],temp = nums[pos];
if(k%n == 0) return;
while (n-- != 0) {
pos = (pos + k) % len;
temp = nums[pos];
nums[pos] = pre;
pre = temp;
if (pos == i) { // 避免陷入循环
pos = ++i;
pre = nums[pos];
temp = nums[pos];
}
}
}
}
方法3:借助另外一个数组保存每次移动的数——以空间换时间
class Solution {
public void rotate(int[] nums, int k) {
// 双数组:顺序 轮转法——借助另一个数组。
int len=nums.length;
int[] res=Arrays.copyOf(nums,len);
int next;
for(int i=0;i
方法4:翻转数组——有点巧妙的
class Solution {
public void rotate(int[] nums, int k) {
// 4.三次翻转数组,找出k%n的那个位置点——耗时最少
int len=nums.length;
int pos=k%(len);
reverse(nums,0,len);
reverse(nums,0,pos);
reverse(nums,pos,len);
}
public void reverse(int[] nums,int start,int end){
int tmp;
int i=0;
while(i<(end-start)/2){
tmp=nums[end-1-i];
nums[end-1-i]=nums[start+i];
nums[start+i]=tmp;
i++;
}
}
}
方法5:每次向前移动一位,重复k次(超出时间限制)
class Solution {
public void rotate(int[] nums, int k) {
// 3.单次轮转k次法O(n*k)——超出时间限制×
int len=nums.length;
int tmp;
while((k--)!=0){
tmp=nums[0];
for(int i=1;i
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)