给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
进阶:
尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?
作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
一开始想到了构建一个新数组作为结果,然后每个元素直接按(当前位置 + k)% length 得到右移之后的新位置放到新数组内作为结果返回。
不过这个方法显然不能原地工作Orz。
于是又想到可以只用一个临时变量存储队尾元素,然后每个元素右移一位,最后临时变量放置到对头,这样进行k轮。结果这种方法还超时了。。。
/** * 向右移动元素,每次移动一位,移动k次 * 从后向前开始移动,所以暂存队尾元素,一轮移动完毕后,暂存元素放至队首 * @param nums * @param k */ public static void rotate(int[] nums, int k){ int len = nums.length; if(len <= 1){ return; } while(k > 0){ int temp = nums[len - 1];//暂存最后一位元素 for(int i = len - 2; i >= 0; i--){ //从倒数第二位元素开始,依次右移 nums[i + 1] = nums[i]; } nums[0] = temp; k--; } }
然后看一下题解,竟然翻转三次数组就可以办到!
/** * 反转三次 * 1.整体反转1次 * 2.前k个元素反转依次 * 3.其余元素反转一次 * 上述步骤相当于所有元素右移k位 * @param nums * @param k */ public static void rotate(int[] nums, int k){ int len = nums.length; if(len <= 1){ return; } k %= len; reverse(nums,0, nums.length - 1); reverse(nums, 0, k - 1); //前k个元素对应的下标 个数转下标要-1 reverse(nums, k, nums.length - 1); } /** * 反转数组[begin, end]范围内的元素 * @param array * @param begin * @param end */ public static void reverse(int[] array, int begin, int end){ while(begin < end){ int temp = array[end]; array[end--] = array[begin]; array[begin++] = temp; } }
这个方法真的太妙了,那若是数组左移k位怎么办呢?只需要旋转后k个元素和其余元素就可以,代码如下
/** * 1.数组整体反转一遍 * 2.第二次反转后k个元素 * 3.第三次反转剩余元素 * @param nums * @param k */ public static void rotate2(int[] nums, int k){ int len = nums.length; if(len <= 1){ return; } k %= len; int d = len - k; //此时d之后有k个元素,故d为分界线 reverse(nums,0, len - 1); reverse(nums, 0, d - 1); //前k个元素对应的下标 个数转下标要-1 reverse(nums, d, len - 1); }