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];
    }

  • 0
    E

    So instead of doing a deep copy at the end, I basically set the reference and it did not work:

    class Solution {
    public void rotate(int[] nums, int k) {
    int[] a = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
    a[(i + k) % nums.length] = nums[i];
    }
    nums = a;
    }
    }

    I thought arrays were objects in Java and thus reference types.


  • 0
    X

    A stupid way
    void rotate(vector<int>& nums, int k) {
    int n=nums.size();
    int count=(k%n==0 ? 0:n-k%n);
    for(int i=0;i<count;i++){
    nums.push_back(nums[i]);
    }
    nums.erase(nums.begin(),nums.begin()+count);
    }


  • 0
    Y

    @emkk Hey dude, I have the same quesiont with you. Took me some while but check this out https://leetcode.com/playground/new

    See how the main class call the solution, it is passing an array to nums, thus any redirect of nums only change what it is points to, we have to make sure the ORIGINAL array object is changed, not redirecting the reference.


  • 0
    Y

    @emkk Update, the link I put in the initial reply not valide. You have to click the >_ icon in the question to enter mode Debug Code in playground and view the code for main class there.


Log in to reply
 

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