189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input:

[1,2,3,4,5,6,7] and

k

 = 3

Output:

[5,6,7,1,2,3,4]

Explanation:

rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input:

[-1,-100,3,99] and

k

 = 2

Output:

 [3,99,-1,-100]

Explanation:

 rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Note:

  • Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
  • Could you do it in-place with O(1) extra space?

 

In place rotate

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return NULL
     */
    function rotate(&$nums, $k) {
        $c = count($nums);
        $steps = 0;
        $start = 0;
        
        while($steps < $c){  
            $i = $start;
            $prev = $nums[$i];
            do{         
                $next = ($i+$k)%$c;
                $temp = $nums[$next];
                $nums[$next] = $prev;
                $prev = $temp;
                $i += $k;
                $i = $i % $c;
                $steps++;
            }while($start != $i);
            $start ++;
            
        }
    
    }
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.