leetcode 189
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
示例 1:
输入:[1,2,3,4,5,6,7]
和 k = 3 输出:[5,6,7,1,2,3,4]
解释: 向右旋转 1 步:[7,1,2,3,4,5,6]
向右旋转 2 步:[6,7,1,2,3,4,5]
向右旋转 3 步:[5,6,7,1,2,3,4]
先把前n-k个数字转置,再把后k个数字转置 再把全部数字转置
需要注意 k = k % A.length;比如k=3 A={1,2} 这样相当于k=1
class Solution { public void rotate(int[] nums, int k) { if(nums == null || nums.length == 0 || k % nums.length == 0) return; int turns = k % nums.length; int middle = nums.length - turns; reverse(nums, 0, middle-1); // reverse left part reverse(nums, middle, nums.length-1); // reverse right part reverse(nums, 0, nums.length-1); // reverse whole part } private void reverse(int[] A,int startIndex,int endIndex) { while (endIndex > startIndex) { int temp = A[startIndex]; A[startIndex] = A[endIndex]; A[endIndex] = temp; startIndex++; endIndex--; } } }
方法二 暴力解法 循环k次移位 每次向右移一位 leetcode过了 leetcode-cn超时
class Solution { public void rotate(int[] nums, int k) { if(nums == null || nums.length == 0 || k % nums.length == 0) return; k = k % nums.length; for (int j = 0; j <k;j++) { int first = nums[nums.length-1]; for (int i = nums.length-1 ; i > 0;i--){ nums[i] = nums[i-1]; } nums[0]=first; } } }