Java cyclic replacement solution, O(n) time O(1) space without reverse.


  • 0

    I noticed the highest votes are using reverse. They are quite brilliant. But I am not...
    Here is my non-reverse solution.
    My logic is just rotation as it is required.
    For example, nums = {1,2,3,4}. k = 2. It should be {3,4,1,2}.
    Let's see what happens to each entry. At index 0, 1->3 and at index 2, 3->1. It is a cycle right? Just memorize the start entry of the cycle as temp and do the cycle swap. At the end, when the index comes back to the start of the cycle, replace it with temp value. And how many cycles there are, for this example, 2 cycles. So for the outer loop, it should be cycles < k? nah. The cycles come out when n % k == 0. Otherwise, there is only one cycle.
    For example, if nums = {1,2,3} and k = 2. It should be {2,3,1}. There is only one cycle for this example. Since of that, it is easier to track how many numbers are already swapped. If the count reaches n, the outer loop stops.
    Here is the code.
    By the way, some people may doubt why it is O(n) not O(n^2). It happened before because they see there are 2 loops. As you see, the total number of the loops are restricted by one value: count. Count will not be bigger than n. Also, the formula i = (i+n-k) % n makes sure it cannot reach the universe. It is O(n).
    Edit: Well, I just noticed there is already a set of solutions for this problem including this way.
    Please check: https://leetcode.com/problems/rotate-array/solution/#approach-3-using-cyclic-replacements-accepted

    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int start = 0;
        int count = 0;
        while (count < n) {
            int i = start;
            int temp = nums[start];
            while ( (i + n - k) % n != start ) {
                nums[i] = nums[ (i + n - k) % n ]; 
                i = (i + n - k) % n;
                count++;
            }
            nums[i] = temp;
            count++; // Do not forget this count++ for the last swap in the cycle.
            start++;
        }
    }

Log in to reply
 

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