No reverse O(n) time O(1) space solution


  • 2
    R
    public class Solution {
        public void rotate(int[] nums, int k) {
            int index = 0;
            int distance = 0;
            int cur = 0;
            for (int i = 0; i < nums.length; i++){
                int next = (index+k)%nums.length;
                int temp = nums[next];
                nums[next] = nums[cur];
                nums[cur] = temp;
                index = next;
    
                distance=(distance+k)%nums.length;
                if (distance == 0){
                    index = (index+1)%nums.length;
                    cur = index;
                }
            }
        }
    }

  • 0
    H

    awesome, but can you explain the algorithm? It's looks have a high performance but I cannot figure out how to implement it.


  • 0
    L

    The idea of this algorithm is that at each iteration, you move an element to the correct position by swapping two numbers. Then, move the element that was swapped out to the correct position, swapping out the next one, and repeat. However, in the case that the loop wrapped back to itself (similar problem with hash table collisions) you can end up never touching some of the elements unless you check for a loop and increment the index.


Log in to reply
 

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