Rotate Array


  • 0

    Click here to see the full article post


  • 0
    D

    For solution 3: isn't it n-elements are reversed a total of 2 times?
    1st: n-elements
    2nd: n-k elements
    3rd: k elements
    total: = n + n - k + k = 2n ?


  • 0
    T

    No, it is just one pass as we a have a count variable that keeps tracks of the items replaces so far.


  • 0
    C

    Let n=7 and k=2.

    Original List                   : 1 2 3 4 5 6 7
    After reversing all numbers     : 7 6 5 4 3 2 1
    After reversing first k numbers : 6 7 5 4 3 2 1  
    After revering last n-k numbers : 6 7 1 2 3 4 5 --> This is not the Result
    
    Solution lacks a step!!
    

  • 0
    T

    if (nums.empty() || (k %= nums.size()) == 0) return;
    int n = nums.size();
    reverse(nums.begin(), nums.begin() + n - k);
    reverse(nums.begin() + n - k, nums.end());
    reverse(nums.begin(), nums.end());


  • 0

    I wrote something to help understanding the third Cyclic Replacements approach:interpretation/proof


  • 0
    O

    var rotate = function(nums, k) {
    for (var i = 0; i < k; i++){
    nums.unshift(nums.pop())
    }
    };

    In JavaScript


  • 0
    P

    Consider the following enhanced version of Approach #3 Using Cyclic Replacements in C++.

    It first converts the problem into the equivalent rotation to the left of n - (k % n) positions. Then rotate each cycle directly in the vector, storing in the temp variable the first element only.

    class Solution {
    public:
        
        void rotate(vector<int>& nums, int k) {
            int n = nums.size();
            k = n - (k % n);
            
            int count = 0;
            for (int begin = 0; count < n; begin++) {
                int temp = nums[begin];
                
                int curr = begin;
                for (int next = (curr + k) % n; next != begin; next = (curr + k) % n) {
                    nums[curr] = nums[next];
                    curr = next;
                    count++;
                }
                
                nums[curr] = temp;
                count++;
            }
        }
    };
    

  • 0
    Z

    This solution doesn't work for the following condition
    Input: array: [1,2,3,4,5] and k = 4
    Output: [5,1,2,3,4]
    Could anyone tell me what is the issue with this code?

    def rotateArray(nums, k):
    
        k = k%len(nums)
        end = len(nums) - 1
    
        if k is None or k<= 0:
            return
    
        reverse(nums, 0, end - k)
        reverse(nums, end - k + 1, end)
        return reverse(nums, 0, end)
    
    def reverse(nums, start, end):
        while start < end:
            nums[start], nums[end] = nums[end],nums[start]
            start += 1
            end -= 1
        return nums
    
    print rotateArray([1,2,3,4,5], 4)

  • 0
    C

    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.
    """
    list=[]
    for i in range(k):
    nums.insert(0,nums.pop())


  • 0
    P
    //Example for Rotate Array in C [Accepted]
    void rotate(int* nums, int numsSize, int k) {
        int *nArry = malloc(numsSize*sizeof(int));
        if(numsSize<k)
            k %= numsSize;
        for(int i=0; i<numsSize; i++)
            if(i<(numsSize-k))
                nArry[i+k] = nums[i];
            else
                nArry[i-(numsSize-k)] = nums[i];
        for(int i=0; i<numsSize; i++)
            nums[i]=nArry[i];
    }

Log in to reply
 

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