开发 网站 费用,广告页面制作,重庆帝一网络网站建设专家,哪个做问卷网站佣金高题目描述 给定一个数组#xff0c;将数组中的元素向右移动 k 个位置#xff0c;其中 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]示…题目描述 给定一个数组将数组中的元素向右移动 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]示例 2:
输入: [-1,-100,3,99] 和 k 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]说明:
尽可能想出更多的解决方案至少有三种不同的方法可以解决这个问题。要求使用空间复杂度为 O(1) 的原地算法。
我的思路
一次到位移动k个位置一次移动一个位置循环k次
两种思路乘以移动方向左移、右移共四种结题思路。 举例一次到位右移k次PS空间复杂度不符合要求…
public void rotate(int[] nums, int k) {if(nums null || nums.length1 || k%nums.length0) {return;}kk%nums.length;int curValnums[0],nextVal0,curIdx0,nextIdx0,count0;SetInteger set new HashSetInteger();set.add(0);while(countnums.length) {nextIdx (curIdxk)%nums.length;nextVal nums[nextIdx];nums[nextIdx] curVal;if(set.contains(nextIdx)) {//防止出现n%k0时的死循环现象for(int i1;inums.length;i) {if(!set.contains(i)) {curVal nums[i];curIdx i;set.add(curIdx);break;}}}else {curVal nextVal;curIdx nextIdx;set.add(curIdx);}}}思路2 一次移动一个位置循环k次
这个思路实现起来最简单但是相应的时间复杂度也较高O(k*n)
/*** 双重循环* 时间复杂度O(k*n)* 空间复杂度O(1)*/
public void rotate(int[] nums, int k) {if(nums null || nums.length1 || k%nums.length0) {return;}kk%nums.length;int len nums.length;int temp0;for(int i0;ik;i) {temp nums[len-1];for(int jlen-1;j0;j--) {nums[j] nums[j-1];}nums[0] temp;}}拓展后
思路3翻转数组 /*** 翻转* 时间复杂度O(n)* 空间复杂度O(1)*/
public void rotate(int[] nums, int k) {if(nums null || nums.length1 || k%nums.length0) {return;}int n nums.length;k % n;reverse(nums, 0, nums.length-1);reverse(nums, 0, k-1);reverse(nums, k, nums.length-1);}private void reverse(int[]nums, int start, int end) {int temp0;while(startend) {tempnums[start];nums[start]nums[end];nums[end--]temp;}}网上大神的代码摘录如下
/*** 双重循环* 时间复杂度O(kn)* 空间复杂度O(1)*/public void rotate_1(int[] nums, int k) {int n nums.length;k % n;for (int i 0; i k; i) {int temp nums[n - 1];for (int j n - 1; j 0; j--) {nums[j] nums[j - 1];}nums[0] temp;}}/*** 翻转* 时间复杂度O(n)* 空间复杂度O(1)*/public void rotate_2(int[] nums, int k) {int n nums.length;k % n;reverse(nums, 0, n - 1);reverse(nums, 0, k - 1);reverse(nums, k, n - 1);}private void reverse(int[] nums, int start, int end) {while (start end) {int temp nums[start];nums[start] nums[end];nums[end--] temp;}}/*** 循环交换* 时间复杂度O(n^2/k)* 空间复杂度O(1)*/public void rotate_3(int[] nums, int k) {int n nums.length;k % n;// 第一次交换完毕后前 k 位数字位置正确后 n-k 位数字中最后 k 位数字顺序错误继续交换for (int start 0; start nums.length k ! 0; n - k, start k, k % n) {for (int i 0; i k; i) {swap(nums, start i, nums.length - k i);}}}/*** 递归交换* 时间复杂度O(n^2/k)* 空间复杂度O(1)*/public void rotate(int[] nums, int k) {// 原理同上recursiveSwap(nums, k, 0, nums.length);}private void recursiveSwap(int[] nums, int k, int start, int length) {k % length;if (k ! 0) {for (int i 0; i k; i) {swap(nums, start i, nums.length - k i);}recursiveSwap(nums, k, start k, length - k);}}private void swap(int[] nums, int i, int j) {int temp nums[i];nums[i] nums[j];nums[j] temp;}
