[算法面试题]-用Java旋转数组

题目

例如，在n = 7和k = 3的情况下，数组[1,2,3,4,5,6,7]旋转为[5,6,7,1,2,3,4]。您知道多少种不同的方法可以解决此问题？

参考解决方案

解决方案1-中间阵列

我们可以直接创建一个新数组，然后将元素复制到该新数组。然后使用更改原始数组

System.arraycopy()

代码示例：

public void rotate(int[] nums, int k) {
    if(k > nums.length) 
        k=k%nums.length;
 
    int[] result = new int[nums.length];
 
    for(int i=0; i < k; i++){
        result[i] = nums[nums.length-k+i];
    }
 
    int j=0;
    for(int i=k; i<nums.length; i++){
        result[i] = nums[j];
        j++;
    }
 
    System.arraycopy( result, 0, nums, 0, nums.length );
}

解决方案2-气泡旋转

我们可以在O（1）空间中这样做吗？
这个解决方案就像一个冒泡排序。

public static void rotate(int[] arr, int order) {
	if (arr == null || order < 0) {
	    throw new IllegalArgumentException("Illegal argument!");
	}
 
	for (int i = 0; i < order; i++) {
		for (int j = arr.length - 1; j > 0; j--) {
			int temp = arr[j];
			arr[j] = arr[j - 1];
			arr[j - 1] = temp;
		}
	}
}

但是，时间为O（n * k）。

这是一个算法的运行过程示意（长度= 7，顺序= 3）：

i = 0 
0 1 2 3 4 5 6 
0 1 2 3 4 6 5 
... 
6 0 1 2 3 4 5 
i = 1 
6 0 1 2 3 5 4 
... 
5 6 0 1 2 3 4 
i = 2 
5 6 0 1 2 4 3 
... 
4 5 6 0 1 2 3 

解决方案3-倒转

我们可以在O（1）空间和O（n）时间中做到这一点吗？以下解决方案可以。
假设给定{1,2,3,4,5,6}和阶数2。基本思想是：

1.将数组分为两部分：1、2、3、4和5、6 
2.反转第一部分：4、3、2、1、5、6 
3.反转第二部分：4、3、2、1， 6,5 
4.反转整个数组：5,6,1,2,3,4

代码示例：

public static void rotate(int[] arr, int order) {	
	if (arr == null || arr.length==0 || order < 0) {
		throw new IllegalArgumentException("Illegal argument!");
	}
 
	if(order > arr.length){
		order = order %arr.length;
	}
 
	//length of first part
	int a = arr.length - order; 
 
	reverse(arr, 0, a-1);
	reverse(arr, a, arr.length-1);
	reverse(arr, 0, arr.length-1);
 
}
 
public static void reverse(int[] arr, int left, int right){
	if(arr == null || arr.length == 1) 
		return;
 
	while(left < right){
		int temp = arr[left];
		arr[left] = arr[right];
		arr[right] = temp;
		left++;
		right--;
	}	
}

 

---