My Java implementation using O(1) space performs quite slow


  • 0
    N

    My Java implementation is as follow

    public class Solution {
        public void rotate(int[] nums, int k) {
            int n = nums.length;
            k = k % n;
            if (k == 0)
                return;
            int index = 0, val = nums[index], counter = 0;
            int lastBegin = 0, targetIndex;
            while (counter < n) {
                targetIndex = (index + k) % n;
                int tempVal = nums[targetIndex];
                nums[targetIndex] = val;
                if (targetIndex == lastBegin) {
                    index = (targetIndex + 1) % n;
                    val = nums[index];
                    lastBegin = index;
                }
                else {
                    index = targetIndex;
                    val = tempVal;
                }
                counter++;
            }
        }
    }
    

    the runtime is about 375ms, it is below the average Java solution performance. I don't quite understand why it is so slow.


  • 0
    J

    Because everytime it moves only one

    if (targetIndex == lastBegin) {
                    index = (targetIndex + 1) % n;
                    val = nums[index];
                    lastBegin = index;
                }
    

    what does this part of code do ?


  • 0
    N

    What I do is move an element to the right position that is its index plus k. Depending on the value of k, the moving process may has many rounds. I use lastBegin to keep track of the first element in a round. If the targetIndex is equal to lastBegin, then this round is finished, the process should move to the next round, starting from (targetIndex+1)%n.


Log in to reply
 

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