Java In-place without 3 reverse().. Google asked this as a follow up


  • 1

    Google asked this one as a follow up, just do that without using the normal 3 reverse way.
    k = 3
    1 2 3 4 5 6 7 = > 5 6 7 1 2 3 4
    1 2 3 1 5 6 7 t = 4
    1 2 3 1 5 6 4 t = 7
    1 2 7 1 5 6 4 t = 3
    1 2 7 1 5 3 4 t = 6
    1 6 7 1 5 3 4 t = 2
    1 6 7 1 2 3 4 t = 5
    5 6 7 1 2 3 4..done..

    Looks like just move everyone to right K times, totoaly nums.length times and we are done.

    but
    k = 2
    1 2 3 4 = > 3 4 1 2
    1 2 1 4 t = 3
    It seems there will be a moment we will reach a position we have already been here before.
    Let's just go to next one when we reach a visited position and see what happend..

    And that's it.. I am lucky enough to find a way without abstracting a math modeling, maybe someone can explain this model.

    Just a simple version to illustrate the idea, code could definitely be shorter and clearner.

    public class Solution {
        public void rotate(int[] nums, int k) {
            if (nums.length == 0 || k % nums.length == 0) return;
            k %= nums.length;
            int done = 0;
            for (int i = 0; i < k; i++) {
                int j = i;
                int tempVal = nums[i];
                while (done < nums.length) {
                    int tempJ = (j + k) % nums.length;       // next location
                    int temp = nums[tempJ];
                    nums[tempJ] = tempVal;
                    tempVal = temp;
                    j = tempJ;
                    done++;
                    if (j == i) break;   // about to go to a visitd location.
                }
            }
        }
    }
    

Log in to reply
 

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