每日算法题 13---189.轮转数组

题目189.轮转数组要求给定一个整数数组nums将数组中的元素向右轮转k个位置其中k是非负数。进阶尽可能想出更多的解决方案至少三种示例示例 1: 输入: nums [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] 示例 2: 输入nums [-1,-100,3,99], k 2 输出[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]思路1使用新数组我们可以使用额外的数组来将每个元素放至正确的位置新数组元素规则将原数组下标为i的元素放至新数组下标为ikmod n的位置最后将新数组拷贝值原数组即可可以知道创建新数组要申请空间因此该思路的空间复杂度为On又因为用到了for循环因此时间复杂度为On代码1class Solution { public void rotate(int[] nums, int k) { int n nums.length; int[] newArr new int[n]; for (int i 0; i n; i) { newArr[(i k) % n] nums[i]; } System.arraycopy(newArr, 0, nums, 0, n); } }思路2数组反转我们可以先将所有元素反转这样尾部 k mod n 个元素就被移至数组头部然后我们再反转[0,kmodn−1] 区间的元素和 [kmodn,n−1] 区间的元素即能得到最后的答案。举一个例子n7k3代码2class Solution { public void rotate(int[] nums, int k) { k % nums.length; reverse(nums, 0, nums.length - 1); reverse(nums, 0, k - 1); reverse(nums, k, nums.length - 1); } public void reverse(int[] nums, int start, int end) { while (start end) { int temp nums[start]; nums[start] nums[end]; nums[end] temp; start 1; end - 1; } } }小舟有话说如果觉得有帮助那就点点赞点点关注吧~