数组循环移位

 

public class ArrayCyclicShift {

	/**
	 * 设计一个算法，把一个含有N个元素的数组循环右移K位，要求时间复杂度为O(N),且只允许使用两个附加变量
	 * 假设把abcd1234循环右移4位
	 */
	public static void main(String[] args) {
		
		char[] A = {'a','b','c','d','1','2','3','4'};
		System.out.println("The Original Array is : " );
		Print(A);
		arrayCyclicShift(A,A.length,4);
		System.out.println("The Array After Shift is : ");
		Print(A);

	}

	public static void arrayCyclicShift(char[] A, int N, int K){
		Reverse(A,0,N-K-1);
		Reverse(A,N-K,N-1);
		Reverse(A,0,N-1);
	}
	
	public static void Reverse(char[] A, int start, int end){
		for(;start<end;start++,end--){
			char temp = A[start];
			A[start] = A[end];
			A[end] = temp;
		}
	}
	
	public static void Print(char[] A){
		for(int i=0;i<A.length;i++)
			System.out.print(A[i]);
		System.out.println();
		
	}
}

 

 

评论

1 楼 CUStudent 2012-04-01  

注意K可能大于N，所以，你需要mod一下N，即K=K%N。这样就完全对了！:)