[LeetCode]Rotate Array

题意:给定一个数组,求该数组向右平移k个位置之后的数组,例如:[1,2,3,4,5,6,7] k = 3 => [5,6,7,1,2,3,4,5,6]思路1:最简单的想法必然是暴力啊,一个个的平移,复杂度O(K*N),代码简洁,也能够通过代码1: public void rotate3(int [] nums, int k){//一次移动一个if(k ==0 )return;if(k > nums.length){k = k % nums.length;}int temp = 0;while (k — > 0){temp = nums[nums.length – 1];System.arraycopy(nums, 0 ,nums,1,nums.length-1);nums[0] = temp;}}

思路2:以空间换时间,把最後面的k字符复制到新数组的前面,然后复制其他部分,复杂度both时间和空间O(N)代码2: public void rotate2(int [] nums, int k){//开辟新数组if(k ==0 )return;if(k > nums.length){k = k % nums.length;}int []rs = new int[nums.length];int start = nums.length – k;System.arraycopy(nums, start, rs, 0, k);System.arraycopy(nums, 0, rs, k, rs.length – k);System.arraycopy(rs, 0, nums,0, rs.length);}思路3:我们可以先看个例子,[1,2,3,4,5,6,7] k = 3,可以这样做:1.[5,6,7,4,1,2,3] 先对k个元素做交换,然后我们可以看到[4,1,2,3],这个结构也很熟悉和没处理之前的结构类似,只不过是长度变成4,k变成了1,那么其他的一样,由此我们可以不断更新k和length然后重复1的操作即可复杂度O(N),代码3: public void rotate1(int [] nums, int k){//不断向右平移if(k ==0 )return;if(k > nums.length){k = k % nums.length;}int front = 0;int end = nums.length – k;int temp;int curLength = nums.length;while (front < nums.length -1 ){int nextK = 0;//下一个平移长度if(k > curLength – k && curLength-k > 0){nextK = k % (curLength -k);if(nextK == 0)nextK = curLength – k;} else if(curLength – k == 0){return;}else {nextK = k;};for(int i =0; i < k; ++i){if(front >= nums.length || end >= nums.length)break;temp = nums[front];nums[front] = nums[end];nums[end] = temp;front ++;end ++;}if(front == nums.length -1) break;curLength = curLength-k;k = nextK ;end = nums.length – k;}}思路4: 这个思路我之前是没想到的1.逆转整个数组:[1,2,3,4,5,6,7] –> [7,6,5,4,3,2,1]2.逆转前K个元素:[7,6,5,4,3,2,1] –> [5,6,7,4,3,2,1]3.逆转length-k个元素:[5,6,7,4,3,2,1] –>[5,6,7,1,2,3,4]代码4: public void rotate4(int [] nums, int k){//一次移动一个if(k ==0 )return;if(k > nums.length){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){int temp = 0;while (start <= end){temp = nums[start];nums[start] = nums[end];nums[end] = temp;start ++;end –;}}

，我知道有一种爱情，叫做与你白头，有一种幸福，叫做和你相伴。