最大公约数的应用 - 分享

所用的空间为：number.length + tmep.length。
请问哪里超了？

第一题，加一个额外变量，记下当然开始的位置。什么都不做都可以。

这道题是我在腾讯实习笔试的时见到过，不过人家要求O(n)时间复杂度，1个辅助空间。

	public void move(int[] data, int step){
		
		int length=data.length;
		if(length==1||length==0)
			return;
		
		int temp1=data[0];
                int temp2;
		for(int idx=0,c=1;c<=length;c++){
			temp2=data[idx=(idx+step)%length];
			data[idx]=temp1;
			temp1=temp2;
		}
		//打印结果
		for(int d:data){
			System.out.print(" "+d);
		}
	}
	
    public static void main(String args[]){
    	int a[]={0,2,5,1,4};
    	new Demo().move(a,6);
    }

上面的算法是O(n)时间复杂度，却用到了两个辅助变量temp1和temp2。

这个有意思

前面有人说过了，前n-k位反转，后k位反转，之后整个数组反转就好。

用的时候从这个位置作为起点，到尾了回到头去，一直再到这个位置位置即可。
何必真的移动数组呢？

数组可以看成向量ab，最终要变成ba

先把a翻转，就是1,2,3,4变成4,3,2,1那种翻转，得到aR
然后把b翻转，得到bR

然后再把整个数组翻转(aRbR)R，就能得到ba

编程珠玑里面介绍的

看看编程珠玑吧！

能否这样考虑，先将01234放入一个队列中，然后如果移动3位的话，poll两次到一个stack中，然后先队列输出，然后stack输出。这样就完成了。
其实就是让队列和堆栈组成一个圆而已。

List aa = new ArrayList();
		Queue aa1 = new PriorityQueue();
		Stack q = new Stack();
		aa.add(0);
		aa.add(4);
		aa.add(3);
		aa.add(2);
		aa.add(1);
		Collections.sort(aa);
		aa1.addAll(aa);

		q.add(aa1.poll());
		q.add(aa1.poll());
		
		System.out.println(aa1.toString());
		System.out.println(q.toString());

public static void main(String[] args) {
        int[] a = { 0, 1, 2, 3}; 
        int n = a.length; 
        int k = 2; 
        int temp = 0;
        int i = 0;
        int j = 0; 

        while (i < n) {
        j = i;
        while ((j + k) % n != i) {
        j = (j + k) % n;
        temp = a[j];
        a[j] = a[i];
        a[i] = temp;
        }

    boolean moved = false;
        do {
          i++;
          moved = false;
          for(int l = 0; l < i; l++){
          int j1 = l;
              while ((j1 + k) % n != l) {
            j1 = (j1 + k) % n;
            if (j1 == i) {
            moved = true;
            break;
            }
            }
              if (moved)
              break;
          }
        } while(moved && i < n);
        }
       
        for(int l : a)
          System.out.println(l);
}

这个应该满足腾讯的要求。用a[i]做了一个临时变量。

自己写的，你想说什么呢