189 Rotate array

---

Original Description. 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]

---

• 要求： 给一个数组， 将该数组向右移动 \(k\) 步。

---

• 返回： 移动后的数组

---

• 例子：
  • input: [1,2,3,4,5,6,7] and k = 3
  • output: [5,6,7,1,2,3,4]

---

Solution

• Brute-force 逐位移动。 time complexity: \(O(len(nums)*k)\), space complexity: \(O(1)\)

  class Solution(object):
    def moveonce(self, nums):
        tmp = nums[-1]
        for i in range(len(nums)-1, 0, -1):
            nums[i] = nums[i-1]
        nums[0] = tmp
        return nums
      
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        for i in range(k):
            nums = self.moveonce(nums)
  

  ---

• solution 2:
  去掉sol1中的外部循环。 time complexity: \(O(len(nums))\), space complexity: \(O(k)\)

  class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        if k!=0 and len(nums)!= 1:
            tmp = nums[-k:]
            for i in range(len(nums)-1, k-1, -1):
                nums[i] = nums[i-k]
            nums[0:k] = tmp
  

---

• solution 3:
  Time complexity: \(O(n)\), Auxiliary Space: \(O(1)\)
  With reference to juggling algorithm.

1. 求len(nums)和k的最大公约数: e.x. GCD = 3 if len(nums) = 12 & k = 3
2. If GCD == 1: 逐位移动（solution 1）
3. else: 将array分为长度为k的chunk
4. 将后面几个chunk的数依次rotate

   e.g. input = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], k = 3, gcd = 3

def leftRotate(nums, k):
    for i in range(gcd(k,len(nums))): 
        # move i-th values of blocks 
        temp = arr[i]
        j = i
        while 1:
            step = j + k #(go to next chunk)
            if step >= len(nums):
                step = step - len(nums)
            if step == i:
                break
            arr[j] = arr[step]
            j = step
        arr[j] = temp
        
#Fuction to get gcd of a and b
def gcd(a, b):
    if b == 0:
        return a;
    else:
        return gcd(b, a%b)
        
#UTILITY FUNCTIONS
#function to print an array 
def printArray(arr, size):
    for i in range(size):
        print ("%d" % arr[i], end=" ")
# Driver program to test above functions 
arr = [1, 2, 3, 4, 5, 6, 7]
leftRotate(arr, 2, 7)
printArray(arr, 7)
# This code is contributed by Shreyanshi Arun