3 lines of C++ in one pass using swap


  • 50
    J

    Every swap will put one number into its correct position, so the running time is O(n)

    For example,

    at first, nums[] is [1,2,3,4,5,6,7], n is 7, k is 3

    after first outer loop, nums[] is [4,1,2,3], n is 4, k is 3

    after second outer loop, nums[] is [4], n is 1, k is 0

    loop ends.

    void rotate(int nums[], int n, int k) {
        for (; k %= n; n -= k)
            for (int i = 0; i < k; i++)
                swap(*nums++, nums[n - k]);
    }

  • 0
    S

    It is a good solution. However, can the array increase like a point?
    I am quite confused about "nums++".


  • 0
    J

    @bblsummer In C/C++, the name of an array is just a pointer to the array.


  • 0
    S
    This post is deleted!

  • 0
    S

    Amazing solution!

    I have read the source code of the stl::rotate function,while using Random Access Iterator,STL has almost the same algorithm like yours,but your code is more simplified.


  • 0
    A

    brilliant idea! Use of characteristics of C makes the code shorter and elegant.


  • 3
    B

    Great solution. The code is simple and the algorithm is difficult to understand.


  • 0
    E

    Could you please give some hints (or materials, links) for us to better understand how this works?


  • 0
    A

    Elegant solution! However, the fourth results in undefined behavior. The side effect of nums++ may (or not, which is what you saw) happen before evaluating nums[n-k].


  • 0
    J

    Thanks for pointing out, here is a version without undefined behavior and probably easier to understand.

    void rotate(int nums[], int n, int k) {
        for (; k %= n; n -= k, nums += k)
            for (int i = 0; i < k; i++)
                swap(nums[i], nums[n - k + i]);
    }

  • 0
    Z

    Yeah, the new solution is much easier to understand. Thank you, sen.


  • 0
    X
    This post is deleted!

  • 0
    C

    You are wrong! In the "rotate" function, nums is just a point that points to an integer, so nums++ is quit reasonable. Of course the array name should not be used like nums++.


  • 15

    Great solution! For those who may have difficulties appreciating the C flavor of the code, I rewrite it in C++, simply using a variable start to record the starting position of nums.

    class Solution { 
    public:
        void rotate(vector<int>& nums, int k) {
            int start = 0, n = nums.size();
            for (; k %= n; n -= k, start += k)
                for (int i = 0; i < k; i++) 
                    swap(nums[start + i], nums[start + n - k + i]);
        }
    }; 

  • 0

    I have no idea the reason why your code works right ! Cound you give more detailed explaination!

    Update ! I have got your idea !

    class Solution 
    {
    public:
        void rotate(int nums[], int n, int k) 
        {
            for (; k = k%n; n -= k, nums += k)
            {
                // Swap the last k elements with the first k elements. 
                // The last k elements will be in the correct positions
                // but we need to rotate the remaining (n - k) elements 
                // to the right by k steps.
                for (int i = 0; i < k; i++)
                {
                    swap(nums[i], nums[n - k + i]);
                }
            }
        }
    };
    

  • 1
    L

    I have no idea why the judgement is k = k % n. Can some one explain this for me?


  • 0
    H

    the judgement is not only executing k=k%n, but also check if the k should not be equal to 0.
    If k is equal to 0, no need to swap (shift zero step does not do any change) , or it will be in the infinite loop.


  • 0
    H

    Java solution:

     public void rotate(int nums[], int k) {
        int n = nums.length;
        k=k%n;
        for (int start=0; start<nums.length && k!=0 ; k = k%n){
            for (int i = 0; i < k; i++) {
                swap(nums, start+i, nums.length-k+i);
            }
            n=n-k;
            start=start+k;
        }
     }
    
    private static void swap(int[] nums, int a, int b){
        int temp = nums[b];
        nums[b]= nums[a];
        nums[a]=temp;
    }

  • 2
    X

    I cannot understand the condition k %= n

    A example that is related to this condition.

    k n nums
    3 8 1,2,3,4,5,6,7,8
    3 5 6,7,8,4,5,1,2,3
    1 2 6,7,8,1,2,3,5,4
    0 1 6,7,8,1,2,3,4,5
    ```````` `````````

    I expect [6,7,8,4,5,1,2,3] becomes [6,7,8,1,2,3,4,5],
    but due to swap, it has to become [6,7,8,1,2,3,5,4] first,
    but k = 1, handles this case subtly.

    Any one can explain this ?


  • 0
    H

    This is such a mysterious solution. Fascinating but convoluted.


Log in to reply
 

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