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例成功,1タイムアウト,速度不足)は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

方法2(成功,2 ms,極速)kの大きさの配列を用いて0−k−1ビットの数字を保存し,その後index=(i+k)mod lengthに従ってkからlength−1ビットの数字を新しい位置に配置し,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--){
        	int index=(i+k)%length;
        	nums[index]=nums[i];		
        }
        for(int i=0;i

方法3、他の人の(とても良くて、1つのtempしか使いません)反転用の空間は1つの変数だけでいいから(あるいは使わなくてもいいので、ビット演算を使えばいいです)配列を2つの部分に分けて、0--length-k-とlength-k-length-1に分けます;2つの部分はそれぞれ反転して、更に全体的に反転して、正しい結果を得ることができます.例:[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の2つは(i+k)mod lengthである

   ：  。
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);
    }