Java solution with O(1) space


  • 12
    M
    public class Solution {
        public void rotate(int[] nums, int k) {
            if (nums == null || nums.length == 0) {
                return;
            }
            k = k % nums.length;
            reverse(nums, 0, nums.length-k-1);
            reverse(nums, nums.length-k, nums.length-1);
            reverse(nums, 0, nums.length-1);
        }
        private void reverse(int[] num, int left, int right) {
            while (left < right) {
                int t = num[left];
                num[left] = num[right];
                num[right] = t;
                left++;
                right--;
            }
        }
    }

  • 0
    C

    can you explain what is the underlying concept/theory of this algorithm?


  • 0
    G

    Could you please explain.


  • 0
    M

    you could easily understand this algorithm by following the algorithm by hand :)


  • 0
    W

    Sure, we can. but it will be better if you can share "the way how" you figure it out, since this is not a straightforward thought


  • 0
    S

    check this link: https://leetcode.com/discuss/27387/summary-of-c-solutions

    1. Reverse the first n - k elements, the last k elements, and then all the n elements.

    Time complexity: O(n). Space complexity: O(1).

    class Solution 
    {
    public:
        void rotate(int nums[], int n, int k) 
        {
            k = k%n;
    
            // Reverse the first n - k numbers.
            // Index i (0 <= i < n - k) becomes n - k - i.
            reverse(nums, nums + n - k);
    
            // Reverse tha last k numbers.
            // Index n - k + i (0 <= i < k) becomes n - i.
            reverse(nums + n - k, nums + n);
    
            // Reverse all the numbers.
            // Index i (0 <= i < n - k) becomes n - (n - k - i) = i + k.
            // Index n - k + i (0 <= i < k) becomes n - (n - i) = i.
            reverse(nums, nums + n);
        }
    };

  • 0

    Hi, shanxin136. Great explanations using changes of indexes :-) But I think you may have made some off-by-1 errors, the first should be i to n - k - 1 - i, the second should be n - k - i to n - 1 - i, and the last reverse should be i to n - 1 - i, which gives the same result as yours.


  • 0

    Yes,your code is the best that I have saw!


Log in to reply
 

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