LeetCode 189: Rotate Array (Java)

发布时间:2019-11-19 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了LeetCode 189: Rotate Array (Java)脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

题目: Rotate an array of n elements to the right by k steps.

For example, wITh n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].


两种解法:

  • 第一种是原地swap,记录下被挤掉的数再接着swap,需要一些时间举栗子探索规律;

  • 第二种是倒三次的方法,如果之前没有准备过,面试中不太可能自己想出来。


解法一(12%):

假设数组为[1,3,5,7,9], k = 2 :
先把1换到5的位置,把5拿着换到9的位置,把9拿着换到3的位置。。。最后7到了1的位置就换完了,貌似计划通啊。
停止条件姑且假设为当置换的数回到数组的首位。
不过换一个栗子上述方法就不通了,比如数组为[1,3,5,7,9,11], k = 2, 换一轮发现结果是[9,3,1,7,5,11]。
这里要从3开始重复一遍上述方法,所以要再套一个loop,i = 0, 停止条件为 最大公约数(数组长度,k)。这样所有的情况都能cover了。

public static void rotate(int[] nums, int k) {     if(nums == null || nums.length <= 1)         return;     k = k%nums.length;      int PRev = 0;     int next = 0;     int maxComm = maxCommonDivisor(k,nums.length);     for(int i = 0; i < maxComm;i++){          prev = nums[i];         int j = i+k;         j %= nums.length;         while(j != i){             next = nums[j];             nums[j] = prev;             prev = next;             j+=k;             j%=nums.length;         }         nums[j] = prev;     }     return; }  private static int maxCommonDivisor(int m, int n){     while (m % n != 0) {         int temp = m % n;         m = n;         n = temp;     }     return n; } 

解法二(12%):

巧妙的reverse三次:
第一次reverse整个数组;
第二次reverse子数组(0,k-1);
第三次reverse子数组(k,length-1)

reverse的函数都是一样的,所以可以写一个helper。

public static void rotate(int[] nums,int k) {     if(nums == null || nums.length <= 1)         return;     k %=nums.length;     if(k == 0)         return;     helper(nums,0,nums.length-1);     helper(nums,0,k-1);     helper(nums,k,nums.length-1); }  public static void helper(int[] nums,int start,int end) {     for(int i = start; i <= (end+start)/2;i++) {         int temp = nums[end+start-i];         nums[end+start-i] = nums[i];         nums[i] = temp;     } } 

最后贴一下最快的code(98%):

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

Reference: 0ms 5-line java

脚本宝典总结

以上是脚本宝典为你收集整理的LeetCode 189: Rotate Array (Java)全部内容,希望文章能够帮你解决LeetCode 189: Rotate Array (Java)所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。