讨论/《初级算法》 - 旋转数组/
《初级算法》 - 旋转数组
共 228 个回复

不要局限思维,可以适当的换种思路。
可以根据结果,换种思路。

  1. 先全部反转,将元素提到最前面
  2. 反转前半部分
  3. 反转后半部分
    然后返回结果
100

1,使用临时数组

可以使用一个临时数组,先把原数组的值存放到一个临时数组中,然后再把临时数组的值重新赋给原数组,重新赋值的时候要保证每个元素都要往后移k位,如果超过数组的长度就从头开始,所以这里可以使用(i + k) % length来计算重新赋值的元素下标
image.png

    public void rotate(int nums[], int k) {
        int length = nums.length;
        int temp[] = new int[length];
        //把原数组值放到一个临时数组中,
        for (int i = 0; i < length; i++) {
            temp[i] = nums[i];
        }
        //然后在把临时数组的值重新放到原数组,并且往右移动k位
        for (int i = 0; i < length; i++) {
            nums[(i + k) % length] = temp[i];
        }
    }


2,多次反转

先反转全部数组,在反转前k个,最后在反转剩余的,如下所示

image.png

    public void rotate(int[] nums, int k) {
        int length = nums.length;
        k %= length;
        reverse(nums, 0, length - 1);//先反转全部的元素
        reverse(nums, 0, k - 1);//在反转前k个元素
        reverse(nums, k, length - 1);//接着反转剩余的
    }

    //把数组中从[startend]之间的元素两两交换,也就是反转
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }


其实还可以在调整下,先反转前面的,接着反转后面的k个,最后在反转全部,原理都一样

    public void rotate(int[] nums, int k) {
        int length = nums.length;
        k %= length;
        reverse(nums, 0, length - k - 1);//先反转前面的
        reverse(nums, length - k, length - 1);//接着反转后面k个
        reverse(nums, 0, length - 1);//最后在反转全部的元素
    }

    //把数组中从[startend]之间的元素两两交换,也就是反转
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }


3,环形旋转

类似约瑟夫环一样,把数组看作是环形的,每一个都往后移动k位,这个很好理解
image.png
image.png
image.png

但这里有一个坑,如果nums.length%k=0,也就是数组长度为k的倍数,这个会原地打转,如下图所示

image.png

对于这个问题我们可以使用一个数组visited表示这个元素有没有被访问过,如果被访问过就从他的下一个开始,防止原地打转。

    public static void rotate(int[] nums, int k) {
        int hold = nums[0];
        int index = 0;
        int length = nums.length;
        boolean[] visited = new boolean[length];
        for (int i = 0; i < length; i++) {
            index = (index + k) % length;
            if (visited[index]) {
                //如果访问过,再次访问的话,会出现原地打转的现象,
                //不能再访问当前元素了,我们直接从他的下一个元素开始
                index = (index + 1) % length;
                hold = nums[index];
                i--;
            } else {
                //把当前值保存在下一个位置,保存之前要把下一个位置的
                //值给记录下来
                visited[index] = true;
                int temp = nums[index];
                nums[index] = hold;
                hold = temp;
            }
        }
    }


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

79
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len=nums.size();
        k%=len;
        if(k==0||len==1) return ;
        int temp;        
        temp=nums[0];
        int count = 0;
        for(int i=k,cnt=0;cnt<len;i+=k,cnt++)
        {
         int t=nums[i%len];
         nums[i%len]=temp;
         temp=t;
         if(i%len==count) 
         {
                count++;
                i = count;
                temp = nums[(i) % len];
         }
        }
        
    }
};

image.png

23
class Solution {
    public void rotate(int[] nums, int k) {
         k = k % nums.length;
        int[] rightpart = Arrays.copyOfRange(nums, nums.length - k, nums.length);
        System.arraycopy(nums, 0, nums, k, nums.length - k);
        System.arraycopy(rightpart, 0, nums, 0, k);
    }
}

执行用时:
0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:
39.1 MB, 在所有 Java 提交中击败了21.16%的用户

20

image.png
厉害,我太菜了,我只想出了一个个位移来做,看了你的这个思路比我的好太多。

14
  1. 每旋转一次,将最后一个值存储,数组依次往后移,最后将存储的值放入a[0],这样的操作执行K次(性能不佳)
  2. k可能大于数组长度,取余
class Solution {
    public void rotate(int[] nums, int k) {
        // k可能大于数组长度,取余
        k = k%nums.length;
        for (int j = 0; j < k; j++) {
            int temp = nums[nums.length-1];
            for (int i = nums.length - 1; i > 0; i--) {
                nums[i] = nums[i-1];
            }
            nums[0] = temp;
        }
    }
}
9
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        nums[:] = nums[len(nums) - k:] + nums[:len(nums) - k]

image.png

11

当 k 很大,数组长度较小。如 k = 100,len(nums) = 5,数组切片会出问题吧。
应该先对 k 处理一下, k %= len(nums)

6

java:
使用长度为k的数组temp存放数组后面k个数,
将前面nums.length - k个数从最右边开始依次向右移动k位,
把temp保存的数插入到数组前面

class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
		int temp[] = new int[k];
		int j = 0;
		for (int i = nums.length - k; i < nums.length; i++) {
			temp[j++] = nums[i];
		}
		for (int i = nums.length - k - 1; i >= 0; i--) {
			nums[i+k] = nums[i];
		}
		for (int i = 0; i < temp.length; i++) {
			nums[i] = temp[i];
		}
    }
}

image.png

4

我太菜了,只想的出一种方法

class Solution {
    //只会基础版,想不出进阶版
    public void rotate(int[] nums, int k) {
        firstAc(nums, k);
        //secondTry(nums, k);
    }

    //第二种, 每次移动一位,循环 k 次 ×××××(太离谱)
    //时间: 266ms   10.57%      O(k*n)=O(n^2)
    //空间: 39MB    33.31%      O(1)
    private void secondTry(int[] nums, int k) {
        int length = nums.length;
        k = k % length;
        if(k == 0) return;
        for(int i = 0;i < k;i++) {
            //移一位
            int temp = nums[length - 1];
            for(int j = length - 1;j > 0;j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = temp;
        }
    }

    //第一次尝试,额外数组 ×××××
    //(1)取余
    //(2)节省空间:
    //可以根据 K 与nums.length/2 的大小来判断是右移 k 位,还是左移 nums.length - k 位
    //
    //时间: 1ms     47.29%  O(n + k) | O(n + length - k)
    //空间: 39.1MB  13.32%  O(k) | O(length - k)
    private void firstAc(int[] nums, int k) {
        k = k % nums.length;
        if(k == 0) return;
        if(k < nums.length / 2) {
            //右移 k 位
            rightMoving(nums, k);
        } else {
            //左移 length - k 位
            leftMoving(nums, nums.length - k);
        }
    }

    //右移
    private void rightMoving(int[] nums, int k) {
        int length = nums.length;
        Deque<Integer> cache = new ArrayDeque<>(length - k);
        int i = 0;
        //1.将 k 个数据保存起来
        for(i = length - k;i < length;i++) {
            cache.push(nums[i]);
        }
        //2.移动
        for(i = length - 1;i >= 0;i--) {
            if(i >= k) {
                nums[i] = nums[i - k];
            } else {
                nums[i] = cache.pop();
            }
        }
    }

    //左移
    private void leftMoving(int[] nums, int k) {
        int length = nums.length;
        Deque<Integer> cache = new ArrayDeque<>(length - k);
        int i = 0;
        //1.将 k 个数据保存起来
        for(i = 0;i < k;i++) {
            cache.add(nums[i]);
        }
        //2.移动
        for(i = 0;i < length;i++) {
            if(i + k < length) {
                nums[i] = nums[i + k];
            } else {
                nums[i] = cache.remove();
            }
        }
    }
}
4