O(1) space, O(n) time, in place, in JAVA


  • 1
    A
    public class Solution {
        public void rotate(int[] nums, int k) {
            int n=nums.length;
            k=k%n;
            int start=0;
            int period=k;
            while (start<period){
                int bak=nums[start];
                int i=start;
                while (true){
                    int j=(i+n-k)%n;
                    if (j==start) break;
                    period=Math.min(period,j);
                    nums[i]=nums[j];
                    i=j;
                }
                nums[i]=bak;
                start++;
            }
        }
    }

  • 0
    D

    It surprisingly doesn't work even though it's considered as an excepted answer. I've added a print statement to the last line:

    public static void rotate(int[] nums, int k) {
        int n=nums.length;
        k=k%n;
        int start=0;
        int period=k;
        while (start<period){
            int bak=nums[start];
            int i=start;
            while (true){
                int j=(i+n-k)%n;
                if (j==start) break;
                period=Math.min(period,j);
                nums[i]=nums[j];
                i=j;
            }
            nums[i]=bak;
            start++;
        }
        System.out.println(Arrays.toString(nums));
    }
    

    I made the function static so I could run them on https://ideone.com. I ran these tests:

    public static void main (String[] args) throws java.lang.Exception
    {
    	int[] nums = {1, 2};
    	rotate(nums, 1);
    	nums = new int[]{1, 2, 3};
    	rotate(nums, 1);
    	rotate(nums, 2);
    	nums = new int[]{1, 2, 3, 4};
    	rotate(nums, 1);
    	rotate(nums, 2);
    	rotate(nums, 3);
    }
    

    And got this as the output:

    [2, 1]
    [3, 1, 2]
    [1, 2, 3] //wrong
    [4, 1, 2, 3]
    [2, 3, 4, 1] //wrong
    [3, 4, 1, 2] //wrong
    

    It appears your solution only works when k is 1. I don't blame you for this though, it doesn't seem like the question has that many test cases to be thorough enough. Not even my own answer works although it is being accepted.


  • 0
    A

    The code is right. The array is rotated more than once.
    [1,2,3] --(k=1)--> [3,1,2] --(k=2)--> [1,2,3]


  • 0
    D

    Judging from the example given on the question I believe there's some confusion about what the method should be doing.

    In the example we have [1,2,3,4,5,6,7] and k = 3. Given your logic, it should be [1,2,3,4,5,6,7] --(k=1)--> [7,1,2,3,4,5,6] --(k=2)--> [5,6,7,1,2,3,4] --(k=3)--> [2,3,4,5,6,7,1]. But the answer is [5,6,7,1,2,3,4]. The example performs k right shifts on nums whereas your answer and the test cases perform k right shifts on nums that has been already been rotated by k-1.


  • 0
    A

    you dont get my point.

    [2, 1]
    [3, 1, 2]
    [1, 2, 3] //wrong // it is correct because it is the result of rotate([3,1,2] , 2)
    [4, 1, 2, 3]
    [2, 3, 4, 1] //wrong
    [3, 4, 1, 2] //wrong


  • 0
    A

    [2, 1]

    [3, 1, 2]

    [1, 2, 3] //wrong //// it is correct because it is the result of rotate([3,1,2] , 2)

    [4, 1, 2, 3]

    [2, 3, 4, 1] //wrong

    [3, 4, 1, 2] //wrong

    You totally dont get my point, "The array is rotated more than once." is what you do in your test code.


Log in to reply
 

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