leetcode-189-旋转数组（ Rotate Array）-java

题目及测试用例

package pid189;
/*旋转数组

给定一个数组，将数组中的元素向右移动 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) 的原地算法。*/


public class main
{

	 public static void main(String[] args) {
	        int[][] testTable = {{1,2,3,4,5,6,7},{-1,-100,3,99},{-1,-100,3,99},{4,6,2,0,-99}};
	        int[] testTable2={3,2,3,6};
	        /*for (int[] ito : testTable) {
	            test(ito);
	        }*/
	        for(int i=0;i<4;i++){
	        	test(testTable[i],testTable2[i]);
	        }
	    }

	    private static void test(int[] ito,int ito2) {
	        Solution solution = new Solution();
	        int rtn;
	        long begin = System.currentTimeMillis();
	        for (int i = 0; i < ito.length; i++) {
	            System.out.print(ito[i]+" ");           
	        }
	        System.out.println(ito2);
	        System.out.println();
	        //开始时打印数组

	        //rtn = 
	        solution.rotate(ito,ito2);//执行程序
	        long end = System.currentTimeMillis();  

	        //System.out.println(ito + ": rtn=" + rtn);
	        //System.out.println(ito + ": rtn=" +rtn);
	      for (int i = 0; i < ito.length; i++) {
	    	  System.out.print(ito[i]+" ");
	      }//打印结果几数组

	        System.out.println();
	        System.out.println("耗时：" + (end - begin) + "ms");
	        System.out.println("-------------------");
	    }

}

           

方法1（33个用例成功，一个超时，速度不够快） 是o（kn）

package pid189;

public class Solution
{
	//第一种  一次一个向右移动1位 循环一圈  总共循环k次
	
	public void rotate(int[] nums, int k) {
        int length=nums.length;
        int tempPrev;
        int tempNext;
        k=k%length;
        
        if (k==0&&length==0&&length==1)
		{
			return;
		}
        
        
        for(int i=0;i<k;i++){
        	// 1 1 3  4
        	tempNext=nums[1];
        	tempPrev=nums[0];
        	for(int j=0;j<length-1;j++){       		
        		nums[j+1]=tempPrev;
        		tempPrev=tempNext;
        		tempNext=nums[(j+2)%length];       		
        	}
        	nums[0]=tempPrev;
        }
		
    }
}
           

方法2（成功，2ms，极快）

使用一个大小为k的数组，保存0-k-1位的数字，然后将k到length-1位的数字按照index=(i+k) mod length 为新位置摆放，然后将temp数组放入新位置

package pid189;


class Solution {
    public void rotate(int[] nums, int k) {
        int length=nums.length;
        if(length==0){
        	return;
        }
        k=k%length;
        if(k==0){
        	return;
        }
        int[] temp=new int[k];
        for(int i=0;i<k;i++){
        	temp[i]=nums[i];
        }
        for(int i=length-1;i>=k;i--){
        	int index=(i+k)%length;
        	nums[index]=nums[i];		
        }
        for(int i=0;i<k;i++){
        	int index=(i+k)%length;
        	nums[index]=temp[i];
        }    	    	    	
    }
}


           

方法3，别人的（非常好，只用1个temp）

因为反转用的空间只用一个变量即可（或者不用也行，使用位运算即可）

将数组分为两部分，分为0——length-k-1和length-k——length-1; 两部分分别反转，再整体反转，就能得到正确的结果。 例子：[1,2,3,4,5,6,7] 和 k = 3 分为[1,2,3,4]和[5,6,7];分别反转后得到[4,3,2,1,7,6,5] 再整体反转得[5,6,7,1,2,3,4] 即为正确得结果

每个数原来应该在的位置是(i+k) mod length

0——length-k-1 就是 length-k-i 再反转 k+i

length-k——length-1 就是 length*2-k-i ,再反转 k+i-length

这两个就是(i+k) mod length

nums = “----->–>”; k =3

result = “–>----->”;

reverse “----->–>” we can get “<–<-----”

reverse “<–” we can get “–><-----”

reverse “<-----” we can get “–>----->”

方法三：翻转。
public class Solution {
    private void reverse(int[] nums, int from, int to) {
        while (from < to) {
            nums[from] ^= nums[to];
            nums[to] ^= nums[from];
            nums[from] ^= nums[to];
            from ++;
            to --;
        }
    }
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        reverse(nums, 0, nums.length-k-1);
        reverse(nums, nums.length-k, nums.length-1);
        reverse(nums, 0, nums.length-1);
    }


           

解法4（别人的）

方法一中使用额外数组的原因在于如果我们直接将每个数字放至它最后的位置，这样被放置位置的元素会被覆盖从而丢失。因此，从另一个角度，我们可以将被替换的元素保存在变量temp中，从而避免了额外数组的开销。

我们从位置0开始，最初令temp=nums[0]。根据规则，位置0的元素会放至(0+k) mod n的位置，令x=(0+k) mod n，此时交换temp和nums[x]，完成位置x的更新。然后，我们考察位置x，并交换temp和nums[(x+k) mod n]，从而完成下一个位置的更新。不断进行上述过程，直至回到初始位置0。

容易发现，当回到初始位置0时，有些数字可能还没有遍历到，此时我们应该从下一个数字开始重复的过程，可是这个时候怎么才算遍历结束呢？我们不妨先考虑这样一个问题：从0开始不断遍历，最终回到起点0的过程中，我们遍历了多少个元素？

由于最终回到了起点，故该过程恰好走了整数数量的圈，不妨设为a圈；再设该过程总共遍历了b个元素。因此，我们有an=bk，即an一定为n和k的公倍数。又因为我们在第一次回到起点时就结束，因此a要尽可能小，故an就是n,k的最小公倍数lcm(n,k)，因此b就为lcm(n,k)/k。

这说明单次遍历会访问到lcm(n,k)/k个元素。为了访问到所有的元素，我们需要进行遍历的次数为gcd(n,k)

其中gcd指的是最大公约数。

如果读者对上面的数学推导的理解有一定困难，也可以使用另外一种方式完成代码：使用单独的变量 count 跟踪当前已经访问的元素数量，当 count=n时，结束遍历过程。

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    public int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }
}