c++ - 数组:左旋转 |破解编码面试Hacker Rank - (因超时而终止)

Question

我是一个非常普通的程序员，我正在尝试通过 Hacker-rank 网站提供的不同挑战来提高我的技能。我试图解决这个数组左旋转算法，并且能够通过每个测试用例，除了最后一个是一个大的数字文件。在做了一些研究后，我发现由于超时错误而终止是由于算法效率不够高，我想黑客等级对每个测试用例都有某种时间限制或速度测试，而我的算法不够快。下面我提供了提出的问题和我实现的代码，如果有人可以帮助我减少优化这个算法(解释!)为什么我的算法比较慢我真的很感激。非常喜欢CK

解释:
对大小为 n 的数组进行左旋操作会将数组的每个元素向左移动 1 个单位。例如，如果对数组 [1,2,3,4,5] 执行 2 次左旋转，则数组将变为 [3,4,5,1,2]。

给定一个包含 n 个整数的数组和一个数字 d，对数组执行 d 次左旋转。然后将更新后的数组打印为一行空格分隔的整数。

输入格式

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

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

输出格式
打印一行 n 个以空格分隔的整数，表示执行 d 次左旋转后数组的最终状态。

样本输入

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 ,3] --> [5,1,2,3,4]

因此，我们将数组的最终状态打印为单行空格分隔值，即 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());
}

希望对您有所帮助!