数组：如何把一个数组循环右移K位_数组右移k位

问题描述：

假设要把数组12345678右移2位，变为78123456。

分析：

方法一：

比较移位前后数组序列的形式，不难看出，其中有两段序列的顺序是不变的，即就是 78 和 123456， 可以把这两段看做两个整体，右移k位就是把数组的两部分交换一下。时间复杂度为O(n)

步骤：

1)逆序数组子序列123456，数组序列的形式为65432178

2)逆序数组子序列78， 数组序列的形式变为65432187

3)全部逆序， 数组序列的形式为78123456

代码：

private void shift_k1(int[] a, int k) {
		int n = a.length;
		k = k % n;
		reverse(a,0,n-k-1);
		reverse(a,n-k,n-1);
		reverse(a,0,n-1);
	}
private void reverse(int[] a, int i, int j) {
		for(; i<j; i++,j--){
			int tmp = a[i];
			a[i] = a[j];
			a[j] = tmp;
		}
	}

方法二：

使用arraylist来存储k位后面的数，数组的前K位依次向后移动k位，最后将集合中的后k位数放到a的前k位中，注意对于K需要%a.length.

代码：

private int[] shift_k(int[] a, int k) {
		k = k % a.length;
		if(k == 0){
			return a;
		}
		ArrayList<Integer> q = new ArrayList<Integer>();
		for(int j=a.length-k; j<a.length; j++){
			q.add(a[j]);
		}
		for(int i=a.length-k-1; i>=0; i--){
			a[i+k] = a[i];
		}
		for(int i=0; i<k; i++){
			a[i] = q.get(i);
		}
		return a;
	}