【LeetCode】算法详解#5 ---轮转数组

1.题目介绍

        给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

2.解决思路

        这道题的解决方法有很多，我这里给大家介绍我使用的方法。题目的意思是，给定一个数组nums，在给定一个非负整数k。我们需要将数组nums的后k位依次放置到数组nums的最前面，也就相当于整体将后面的k位数字与之前的数字交换了位置。所以可以这样思考，因为最终的数组nums它的整体上是有序的，变动的位置也只和k有关，所以可以将最终数组nums分为两部分，一部分是经过k位变化的连续整数，另一部分是没有经过变化或已经经过一整轮替换的整数，注意我这里的意思，我们知道如果k大于数组nums的长度，那么也就是说在轮换的过程中一定会完整的将整个数组轮换完，结果是和原数组顺序一致的，所以我们可以在这个思想上对数组进行考虑时直接跳过整轮替换的过程：所以k%nums.length()的结果才是最终有效的替换过程。考虑到要在原数组上进行操作，我们将两部分看成两个数组，最终复制到原数组nums上即可。

3.步骤讲解

        1.根据k对数组nums取余，计算有效轮转数

        2.定义前缀数组，长度为有效轮转数k；定义后缀数组，其值为原数组nums中除轮转数外的               其他整数

        3.定义计数器并对原数组进行部分遍历，将原数组中最后效轮转数的几位整数赋值给前缀数组

        4.将前缀数组复制到原数组；将后缀数组复制到原数组

4.代码展示

public static void test(int[] nums, int k) {//有效轮转数if (k> nums.length){k = k%nums.length;}        //定义前缀数组int[] pre = new int[k];//定义后缀数组int[] last = Arrays.copyOf(nums, nums.length - k);//计数器int index = 0;//遍历原数组对前缀数组进行赋值for (int i = nums.length-k; i < nums.length; i++) {pre[index] = nums[i];index++;}//将前缀数组复制到原数组numsSystem.arraycopy(pre, 0, nums, 0, k);//将后缀数组复制到原数组numsSystem.arraycopy(last, 0, nums, k, nums.length - k);}

5.执行结果

在leetcode中测试用例平均耗时1ms

内存分布56.05MB