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

1.题目先容

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

• 1 <= nums.length <= 105
  
• -231 <= nums <= 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.代码展示

1. public static void test(int[] nums, int k) {
2.         //有效轮转数
3.         if (k> nums.length){
4.             k = k%nums.length;
5.         }        
6.         //定义前缀数组
7.         int[] pre = new int[k];
8.         //定义后缀数组
9.         int[] last = Arrays.copyOf(nums, nums.length - k);
10.         //计数器
11.         int index = 0;
12.         //遍历原数组对前缀数组进行赋值
13.         for (int i = nums.length-k; i < nums.length; i++) {
14.             pre[index] = nums[i];
15.             index++;
16.         }
17.         //将前缀数组复制到原数组nums
18.         System.arraycopy(pre, 0, nums, 0, k);
19.         //将后缀数组复制到原数组nums
20.         System.arraycopy(last, 0, nums, k, nums.length - k);
21.     }

复制代码

5.执行结果

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

内存分布56.05MB 

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。