from __future__ import print_function # Time: O(n) # Space: O(1) # Rotate an array of n elements to the right by k steps. # # For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]. # # Note: # Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem. class Solution(object): """ :type nums: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ def rotate(self, nums, k): k %= len(nums) self.reverse(nums, 0, len(nums)) self.reverse(nums, 0, k) self.reverse(nums, k, len(nums)) def reverse(self, nums, start, end): while start < end: nums[start], nums[end - 1] = nums[end - 1], nums[start] start += 1 end -= 1 # Time: O(n) # Space: O(1) from fractions import gcd class Solution2(object): """ :type nums: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ def rotate(self, nums, k): def apply_cycle_permutation(k, offset, cycle_len, nums): tmp = nums[offset] for i in xrange(1, cycle_len): nums[(offset + i * k) % len(nums)], tmp = tmp, nums[(offset + i * k) % len(nums)] nums[offset] = tmp k %= len(nums) num_cycles = gcd(len(nums), k) cycle_len = len(nums) / num_cycles for i in xrange(num_cycles): apply_cycle_permutation(k, i, cycle_len, nums) # Time: O(n) # Space: O(1) class Solution3(object): """ :type nums: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ def rotate(self, nums, k): count = 0 start = 0 while count < len(nums): curr = start prev = nums[curr] while True: idx = (curr + k) % len(nums) nums[idx], prev = prev, nums[idx] curr = idx count += 1 if start == curr: break start += 1 # Time: O(n) # Space: O(n) class Solution4(object): """ :type nums: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ def rotate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ nums[:] = nums[len(nums) - k:] + nums[:len(nums) - k] # Time: O(k * n) # Space: O(1) class Solution5(object): """ :type nums: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ def rotate(self, nums, k): while k > 0: nums.insert(0, nums.pop()) k -= 1 if __name__ == '__main__': nums = [1, 2, 3, 4, 5, 6, 7] Solution().rotate(nums, 3) print(nums)