A 7-Line Time O(n) In-Place Solution (No Reversing)


  • 16
    L

    The concise 7-line version.

    Sample [1,2,3,4,5,6,7,8,9] 3    
    The replacing process is as follow:
    1) 1->4->7->1
    2) 2->5->8->2
    3) 3->6->9->3
    public void Rotate(int[] nums, int k) {
        if(nums.Length == 0 || k % nums.Length == 0) return;
        int start = 0, i = start, curNum = nums[i], count = 0;
        while(count++ < nums.Length){
            int tmp = nums[i = (i + k) % nums.Length];
            nums[i] = curNum;
            curNum = i == start ? nums[i = ++start] : tmp;
        }
    }
    

    Below is the elaborated version easier to understand

    public void Rotate(int[] nums, int k) {
        if(nums.Length == 0 || k % nums.Length == 0) return;
        int start = 0, i = start, curNum = nums[i], count = 0;
        while(count < nums.Length){
            i = (i + k) % nums.Length;
            int tmp = nums[i];
            nums[i] = curNum;
            if(i == start){
                start++;
                i = start;
                curNum = nums[i];
            }
            else curNum = tmp;
            count++;
        }
    }

  • 0
    D

    Can you please elaborate on your answer on how you came up with this approach?


  • 0
    H

    Excellent!!!How could you get this idea?


Log in to reply
 

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