What it the difference on these two answers? Mine is not correct while the one I am following is right


  • 0
    Z

    I had this wrong code:

      public void rotate(int[] nums, int k) {
        int L=nums.length;
        int starti =0;
        int counter = 0;
        int currentLoc=0;
        int prevVal=nums[currentLoc];
        k=k%L;
        
        while(counter <L){
            if(currentLoc>=L && currentLoc%L == starti){
                currentLoc = starti++;
                prevVal = nums[currentLoc];
            }
            
            int nextLoc = (currentLoc+k)%L;
            int nextValue = nums[nextLoc];
            nums[nextLoc] = prevVal;
            prevVal = nextValue;
            
            currentLoc +=k;
            counter++;
        }
    }
    

    This code is based on the thought of this one:

    public void rotate(int[] nums, int k) {
    int L=nums.length, counter=0, currentLoc=0, starti=0, prevVal=nums[currentLoc];
    k = k%L;
    while(counter++<L) {
        if(currentLoc>=L && currentLoc%L==starti) { // this handles the case when currentLoc moves back to where started.
            currentLoc = ++starti; 
            prevVal=nums[currentLoc];
        }
    
        int nextLoc = (currentLoc+k)%L; // get index of next location
        int nextVal = nums[nextLoc]; // get value at next location
        nums[nextLoc] = prevVal; // update value at next location
        prevVal = nextVal; // update previous value
    
        currentLoc += k; // move current to next location
    }
    

    }

    Quote the author's idea below:
    The idea is move every item to its desired location at once, that is, we move i to i+k for all L possible i's where L = nums.length. To handle the case of overshooting, i+k is indeed (i+k)%L. We start with i=0 as the first round. It is for sure that after several steps, we have i>=L, meaning we have done with one round. For the next round, i will start from i%L. But hold on, we need to handle one special case, that is when i%L == 0 (meaning that after moving for one round i gets to its starting point). We need to handle this case to avoid infinite loops. This is handled in the if loop in the code. That is, whenever this happens, we simply move i to its next location, i.e., i=i+1. And we also need a variable that stores previous i, which is starti in the code. We use a counter to counter the number of items already moved and stops moving when counter==L, i.e., all items are done moving.

    I will give a simple example of how the idea works with the following array of length 5:

    [1, 2, 3, 4, 5]
    Suppose k=3. i starts from 0:

    current=0, and next=(current+3)%5=3, thus, 4 is replaced with 1 (or 1 is moved to the location of 4). Array becomes:

    [1, 2, 3, 1, 5]

    current=3, and next=(current+3)%5=1, thus 2 is replaced with 4. Array becomes:

    [1, 4, 3, 1, 5]

    current=1 and next=(1+3)%5=4, thus 5 is replaced with 2. Array becomes:

    [1, 4, 3, 1, 2]

    current=4 and next=(4+3)%5=2, thus 3 is replaced with 5. Array becomes:

    [1, 4, 5, 1, 2]

    current=2 and next=(2+3)%5=0, thus 1 is replaced with 3. Array becomes:

    [3, 4, 5, 1, 2] And we are done!


Log in to reply
 

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