Naive solution and improved solution


  • 0

    Here are the solutions that I could come up with, first of which got TLE and the second got AC:

    	/**
    	 * Naive method TLE
    	 * 
    	 * @param nums
    	 * @param k
    	 */
    	public void rotateV1(int[] nums, int k) {
    		k %= nums.length;
    		if (k == 0)
    			return;
    		for (int i = 0; i < k; i++) {
    			int temp = nums[nums.length - 1];
    			for (int j = nums.length - 1; j > 0; j--) {
    				nums[j] = nums[j - 1];
    			}
    			nums[0] = temp;
    		}
    	}
    
    	public void rotateV2(int[] nums, int k) {
    		int len = nums.length;
    		if ((k %= len) == 0)
    			return;
    
    		// copy the first k elements
    		int[] temp = new int[k];
    		for (int i = 0; i < k; i++)
    			temp[i] = nums[i];
    		
    		/* Rotate the remaining elements,
    		 * To avoid overriding the element that
    		 * has not yet been rotated to its final position,
    		 * I start from right to left
    		 */
    		for (int i = len - 1; i >= k; i--)
    			nums[(i + k) % len] = nums[i];
    		
    		/*
    		 * Rotate the first k elements
    		 */
    		for (int i = 0; i < k; i++)
    			nums[(i + k) % len] = temp[i];
    	}
    

    Of course, there must be some better solutions like the one posted here. For convenience, the code is:

    public void rotate(int[] nums, int k) {
            int n = nums.length;
            k = k%n;
            int[] temp = Arrays.copyOfRange(nums, 0, n-k);
            System.arraycopy(nums, n-k, nums, 0, k);
            System.arraycopy(temp, 0, nums, k, n-k);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.