8ms, fast C solution


  • 0
    M

    Time complexity: O(n), n swaps at most, n/2 swaps at least (while k = n / 2),

    Space complexity: O(1)

    Suppose A = [1,2,3,4,5,6], it costs 2 steps to rotate A to right by k = 2 times, as below:

    1. switch [1,2] and [5,6]: A = [5,6,3,4,1,2]
    2. switch [3,4] and [1,2]: A = [5,6,1,2,3,4]

    Suppose A = [1,2,3,4,5,6], it costs 1 steps to rotate A to right by k = 3 times, as below:

    1. switch [1,2,3] and [4,5,6]: A = [4,5,6,1,2,3]

    Suppose A = [1,2,3,4,5,6,7], it costs 4 steps to rotate A to right by k = 3 times, as below:

    1. switch [1,2,3] and [5,6,7]: A = [5,6,7,4,1,2,3]
    2. switch [4] and [3]: A = [5,6,7,3,1,2,4]
    3. switch [3] and [2]: A = [5,6,7,2,1,3,4]
    4. switch [2] and [1]: A = [5,6,7,1,2,3,4]

    Code is:

    void swap(int* a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    
    void rotate_begin_and_end(int* a, int total_size, int rotate_size) {
        for (int i = 0; i < rotate_size; ++i) {
            swap(a, i, total_size - rotate_size + i);
        }
    }
    
    void rotate(int* a, int total_size, int right_size) {
        if (total_size <= 0 || right_size <= 0) {
            return;
        }
    
        right_size %= total_size;
        int left_size = total_size - right_size;
        if (left_size > right_size) {
            rotate_begin_and_end(a, total_size, right_size);
            rotate(a + right_size, left_size, right_size);
        } else if (left_size < right_size) {
            rotate_begin_and_end(a, total_size, left_size);
            rotate(a, right_size, right_size - left_size);
        } else {
            rotate_begin_and_end(a, total_size, right_size);
        }
    }

Log in to reply
 

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