数组：左旋转破解编码面试黑客等级-（因超时终止）

Question

输入格式

第一行包含两个空格分隔的整数，分别表示n（整数的个数）和d（您必须执行的左旋转个数）的值。第二行包含n个空格分隔的整数，描述数组初始状态的各个元素。
约束

1<=n<=10^5
1<=d<=n
1<=ai<=10^6

5 4
1 2 3 4 5

示例输出

5 1 2 3 4

当我们执行d=4次左旋转时，数组将经历以下变化顺序:
[1,2,3,4,5]-->[2,3,4,5,1]-->[3,4,5,1,2]-->[4,5,1,2]-->[5,1,2,3]

因此，我们将数组的最终状态打印为一行空格分隔的值，即5 1 2 3 4。

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

vector<int> array_left_rotation(vector<int> a, int n, int k) {
    int tmp=0,x=0;
    while(x < k){
        tmp = a[0];
        for(int i=0; i < n; i++){
            a[i]=a[i+1];
            if(i+1 == n) a[i]= tmp;
        }
        x++;
    }
    return a;
}

int main(){
    int n;
    int k;
    cin >> n >> k;
    vector<int> a(n);
    for(int a_i = 0;a_i < n;a_i++){
        cin >> a[a_i];
    }
    vector<int> output = array_left_rotation(a, n, k);
    for(int i = 0; i < n;i++)
        cout << output[i] << " ";
    cout << endl;
    return 0;
}

Answer 1

这里是我更高效的算法--

要在位置K处旋转数组（将K元素向左移动到N元素），可以执行以下操作：

1. 反向子阵列ARR[0....k-1]它是O(k)
2. 反向子阵列arr[k....n-1]即O(n-k)
3. 最后，反向子阵列arr[0....n]即O(n)

总体复杂度为O(n)，空间复杂度为常数。

您必须注意像k>=n、k<0等角落情况。

void leftRotate(vector<int>& arr, int k)
{
    int n = (int)arr.size();
    if(k >= n) k = k % n;
    reverse(arr.begin(), arr.begin() + k);
    reverse(arr.begin() + k, arr.end());
    reverse(arr.begin(), arr.end());
}

希望有帮助！