Rotate Array Solutions in C++

// Source : https://leetcode.com/problems/rotate-array/
// Author : Hao Chen
// Date   : 2015-03-30



#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;


void reverseArray(int nums[],int start, int end){
    int temp;
    while(start < end){
        int temp = nums[start];
        nums[start++] = nums[end];
        nums[end--] = temp;
    }
}

/*
 * this solution is so-called three times rotate method
 * because (X^TY^T)^T = YX, so we can perform rotate operation three times to get the result
 * obviously, the algorithm consumes O(1) space and O(n) time
 */

void rotate1(int nums[], int n, int k) {
    if (k<=0) return;
    k %= n; 
    reverseArray(nums, n-k, n-1);
    reverseArray(nums, 0, n-k-1);
    reverseArray(nums, 0, n-1);    
}

/*
 * How to change [0,1,2,3,4,5,6] to [4,5,6,0,1,2,3] by k = 3?
 *
 * We can change by following rules: 
 *
 *     [0]->[3], [3]->[6], [6]->[2],  [2]->[5], [5]->[1], [1]->[4]
 *    
 *
 */
void rotate2(int nums[], int n, int k) {
    if (k<=0) return;
    k %= n;
    int currIdx=0, newIdx=k;
    int tmp1 = nums[currIdx], tmp2; 
    int origin = 0;

    for(int i=0; i<n; i++){

        tmp2 = nums[newIdx];
        nums[newIdx] = tmp1;
        tmp1 = tmp2; 

        currIdx = newIdx;

        //if we meet a circle, move the next one
        if (origin == currIdx) {
            origin = ++currIdx;
            tmp1 = nums[currIdx];
        }
        newIdx = (currIdx + k) % n;

    } 
}

void rotate(int nums[], int n, int k) {
    if (random()%2==0) {
        cout << "[1] ";
        return rotate1(nums, n, k);
    }
    cout << "[2] ";
    return rotate2(nums, n, k);
}

void printArray(int nums[], int n) {
    cout << "[ " ;
    for(int i=0; i<n; i++) {
        cout << nums[i] << ((i==n-1)? " " : ", ");
    }
    cout << "]" << endl;
}

void initArray(int nums[], int n) {
    for(int i=0; i<n; i++) {
        nums[i] = i;
    }
}


int main(int argc, char**argv) {
    
    srand(time(0));

    int nums[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    const int n = sizeof(nums)/sizeof(int);

    for (int i=0; i<n; i++) {
        initArray(nums, n);
        rotate(nums, n, i);
        printArray(nums, n);
    }
    return 0;
}

/// Source : https://leetcode.com/problems/rotate-array/description/
/// Author : liuyubobobo
/// Time   : 2018-08-10

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/// Using Queue
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {
public:
    void rotate(vector<int>& nums, int k) {

        queue<int> q;
        while(k -- && !nums.empty())
            q.push(nums.back()), nums.pop_back();
        for(int i = 0 ; i <= k ; i ++)
            q.push(q.front()), q.pop();

        while(!q.empty())
            nums.insert(nums.begin(), q.front()), q.pop();
        return;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> nums1 = {1, 2, 3, 4, 5, 6, 7};
    Solution().rotate(nums1, 3);
    print_vec(nums1);

    vector<int> nums2 = {1, 2};
    Solution().rotate(nums2, 3);
    print_vec(nums2);

    return 0;
}

/// Source : https://leetcode.com/problems/rotate-array/description/
/// Author : liuyubobobo
/// Time   : 2018-08-10

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/// Using Queue and rotate the elements in original nums
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    void rotate(vector<int>& nums, int k) {

        queue<int> q;
        int kk = k;
        for(int i = (int)nums.size() - 1; i >= 0 && kk --; i --)
            q.push(nums[i]);
        for(int i = q.size() ; i < kk ; i ++)
            q.push(q.front()), q.pop();

        for(int i = (int)nums.size() - k - 1; i >= 0; i --)
            nums[i + k] = nums[i];

        while(!q.empty()){
            k --;
            if(k < 0)
                k += nums.size();
            k %= nums.size();
            nums[k] = q.front();
            q.pop();
        }
        return;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> nums1 = {1, 2, 3, 4, 5, 6, 7};
    Solution().rotate(nums1, 3);
    print_vec(nums1);
    // 5 6 7 1 2 3 4

    vector<int> nums2 = {1, 2};
    Solution().rotate(nums2, 3);
    print_vec(nums2);
    // 2 1

    vector<int> nums3 = {1, 2};
    Solution().rotate(nums3, 2);
    print_vec(nums3);
    // 1 2

    return 0;
}

/// Source : https://leetcode.com/problems/rotate-array/description/
/// Author : liuyubobobo
/// Time   : 2018-08-10

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/// Using O(1) Space but O(n^2) operations
/// Time Complexity: O(n^2)
/// Space Complexity: O(1)
class Solution {
public:
    void rotate(vector<int>& nums, int k) {

        while(k --){
            int t = nums.back();
            for(int i = (int)nums.size() - 2; i >= 0; i --)
                nums[i + 1] = nums[i];
            nums[0] = t;
        }
        return;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> nums1 = {1, 2, 3, 4, 5, 6, 7};
    Solution().rotate(nums1, 3);
    print_vec(nums1);
    // 5 6 7 1 2 3 4

    vector<int> nums2 = {1, 2};
    Solution().rotate(nums2, 3);
    print_vec(nums2);
    // 2 1

    vector<int> nums3 = {1, 2};
    Solution().rotate(nums3, 2);
    print_vec(nums3);
    // 1 2

    return 0;
}

/// Source : https://leetcode.com/problems/rotate-array/description/
/// Author : liuyubobobo
/// Time   : 2018-08-10

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/// Cyclic Replacements
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    void rotate(vector<int>& nums, int k) {

        int start = 0, cur = 0, t = nums[cur];
        for(int i = 0; i < nums.size() ; i ++){
            int next = (cur + k) % nums.size();
            int t2 = nums[next];
            nums[next] = t;
            t = t2;
            cur = next;

            if(cur == start)
                start ++, cur = start, t = nums[cur];
        }
        return;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> nums1 = {1, 2, 3, 4, 5, 6, 7};
    Solution().rotate(nums1, 3);
    print_vec(nums1);
    // 5 6 7 1 2 3 4

    vector<int> nums2 = {1, 2};
    Solution().rotate(nums2, 3);
    print_vec(nums2);
    // 2 1

    vector<int> nums3 = {1, 2};
    Solution().rotate(nums3, 2);
    print_vec(nums3);
    // 1 2

    vector<int> nums4 = {1, 2, 3, 4, 5, 6};
    Solution().rotate(nums4, 3);
    print_vec(nums4);
    // 5 6 1 2 3 4

    return 0;
}

/// Source : https://leetcode.com/problems/rotate-array/description/
/// Author : liuyubobobo
/// Time   : 2018-08-10

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/// Using Reverse
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    void rotate(vector<int>& nums, int k) {

        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }

private:
    void reverse(vector<int>& nums, int start, int end){
        for(int i = start, j = end; i < j; i ++, j --)
            swap(nums[i], nums[j]);
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> nums1 = {1, 2, 3, 4, 5, 6, 7};
    Solution().rotate(nums1, 3);
    print_vec(nums1);
    // 5 6 7 1 2 3 4

    vector<int> nums2 = {1, 2};
    Solution().rotate(nums2, 3);
    print_vec(nums2);
    // 2 1

    vector<int> nums3 = {1, 2};
    Solution().rotate(nums3, 2);
    print_vec(nums3);
    // 1 2

    vector<int> nums4 = {1, 2, 3, 4, 5, 6};
    Solution().rotate(nums4, 2);
    print_vec(nums4);
    // 5 6 1 2 3 4

    return 0;
}