面试经典150题——轮转数组

面试经典150题 day6

• • • 题目来源
    • 我的题解
    • • 方法一 使用额外数组
      • 方法二 循环替换
      • 方法三 数组翻转

题目来源

力扣每日一题；题序：189

我的题解

方法一 使用额外数组

使用一个额外数组暂存最终答案，最后再赋值给nums

时间复杂度：O(n)
空间复杂度：O(n)

public void rotate(int[] nums, int k) {
    int n=nums.length;
    int[] res=new int[n];

    if(k==0)
        return;
    for(int i=0;i<n;i++){
        res[(i+k)%n]=nums[i];
    }
    for(int i=0;i<n;i++)
        nums[i]=res[i];
}

方法二 循环替换

该方法涉及数学知识，比较复杂，详细过程见官方题解

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    public int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }
}

方法三 数组翻转

先翻转整个数组，然后再分别翻转[0,k%n-1]和[n%k,n-1]两个子数组

时间复杂度：O(n)
空间复杂度：O(1)

public void rotate(int[] nums, int k) {
    int n=nums.length;
    //这里数组的长度最大是100000
    int index=k%n;
    if(index==0)
        return;
    reverse(nums,0,n-1);
    reverse(nums,0,index-1);
    reverse(nums,index,n-1);
    
    
}
public void reverse(int[] nums,int start,int end){
    int left=start,right=end;
    while(left<right){
        int t=nums[left];
        nums[left]=nums[right];
        nums[right]=t;
        left++;
        right--;
    }
}

//不知道为什么这样写比上面的快
public void rotate(int[] nums, int k) {
    int index=k%nums.length;
    trverse(nums,0,nums.length-1);
    trverse(nums,0,index-1);
    trverse(nums,index,nums.length-1);
    
}
public void trverse(int[] nums,int start,int end){
    int left=start,right=end;
    while(left<right){
        swap(nums,left++,right--);
    }
}
public void swap(int[] nums,int i,int j){
    if(i==j)
        return ;
    int temp=nums[i];
    nums[i]=nums[j];
    nums[j]=temp;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈????~