My c++ solution, o(n)time && o(1)space


  • 30
    G
    class Solution {
    public:
        void rotate(int nums[], int n, int k) {
            int nowIndex = 0, nextIndex;
    		int tmp1, tmp2 = nums[0];
    		for(int j=0,i=0; j<n; j++){
    			tmp1 = tmp2;
    			nowIndex = (k + nowIndex) % (n);
    			tmp2 = nums[nowIndex];
    			nums[nowIndex] = tmp1;
    			if(nowIndex == i) {
    				nowIndex = ++i;
    				tmp2 = nums[nowIndex];
    			}
    		}
        }
    };

  • 19
    Y

    Excellent Answer. Here I just add some explanations.

    How to change [0,1,2,3,4,5,6] to [4,5,6,0,1,2,3] by k = 3?

    We can change by following rules: [0]->[3], [1]->[4], [2]->[5], [3]->[6], [4]->[0], [5]->[1], [6]->[2]

    Other cases are the same.

    To solve this problem, we should know the following two facts:

    1. We must do exactly n assigned-steps to finish the target.

      see the two figures below. On the right side of each figure shows the same process as left side. The total step is just the number of edges.

    2. We can obtain several self-closed circles when we do the operation.

      By figure we can clearly see it. Each time when we exchange values among a circle, there is no relationship with other circles.Done with this one, we move to another circle.

    class Solution {
    public:
    void rotate(int nums[], int n, int k) {
    
        if(n == 0)return;
        k = k % n;
        
        //initialize
        int i = 0;
        int nowIndex = 0;
        int tmp = nums[0],stmp;
    
        //exactly n steps, n times loop
        for(int j = 0; j < n; j++)
        {
            //next index to exchange
            nowIndex = (nowIndex + k) % n;
    
            //exchange
            stmp = nums[nowIndex];
            nums[nowIndex] = tmp;
            tmp = stmp;
    
            //finish a circle,move to another circle
            if(nowIndex == i)
            {
                nowIndex = ++i;
                tmp = nums[nowIndex];
            }
        }
    }
    

    };


  • 0
    C

    you light me!!!


  • 0
    L

    nowIndex should less than n


  • 0
    L

    Good job. And nowIndex should less than n


  • 0
    Y

    Thanks for your question. I think no need to consider nowIndex is less than n or not. Since you may think "nowIndex = ++i" maybe larger or equal than n, but it is impossible. Because nowIndex is the first position in one circle assignment.The index must appear at front of the array.


  • 0
    L

    [1] k=1 nowIndex can be 1 and nums[nowIndex] out of range


  • 0
    Y

    Thx.Although nums[nowIndex]may out of range, no influence on final result. Besides this, for k>=n,we can always make k = k%n, and if k==0 , array doesn't change. Add this special case may avoid this problem.


  • 0
    L

    yes. And your explanation is excellent.


  • 0
    W

    Thanks a lot for the explanation! But could you tell me, how many "loops" can be in an array? Or,to put it another way, what is the maximum value of the variable i? And how does this value depend on the length of an array and on the value of k? For example,I see,that when k is even there are 2 loops, when odd - 1.Is there any particular rule?


  • 0
    G

    (k + nowIndex) % (n) this is to keep nowindex less than n


  • 0
    N

    @yomin Your image could not be loaded can you please check


Log in to reply
 

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