首页 文章

数组：左旋转|破解编码访谈黑客排名 - （由于超时而终止）

提问于
浏览 次
0

我是一名相当普通的程序员，并且正在尝试通过Hacker-rank网站提供的不同挑战来提高我的技能 . 我试图解决这个数组左旋转算法，并能够通过除最后一个数字大文件之外的每个测试用例 . 经过一些研究后我发现由于超时错误导致的终止是由于算法不够有效，我认为黑客等级对每个测试用例都有某种时间限制或速度测试，而我的算法速度不够快 . 下面我提供了问题和我实现的代码，如果有人可以帮我减少优化这个算法（EXPLAIN！）为什么我的算法速度慢我真的很感激它 . 很多爱CK

说明：
在大小为n的阵列上的左旋转操作将每个阵列的元素1单元向左移位 . 例如，如果在数组[1,2,3,4,5]上执行了2次左旋转，则数组将变为[3,4,5,1,2] .

给定n个整数和数字d的数组，在数组上执行左旋转 . 然后将更新的数组打印为单行空格分隔的整数 .

输入格式

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

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

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

样本输入

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;
}
c++ arrays algorithm

2 回答

  • 3

    这是我更有效的算法 -

    反转算法

    要在 k 位置旋转数组（将 k 移动到左边的 n 元素），我们可以这样做：

    • 反向子阵 arr[0 .... k - 1] 这是 O(k)

    • 反向子阵 arr[k .... n - 1] 这是 O(n - k)

    • 最后，反向子阵 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());
}

    希望能帮助到你！

    回复于
  • 1

    对我来说，任务听起来根本不需要执行旋转 . 你只需要 print 结果，完全跳过旋转！

    基本上您只需要执行以下操作：

    • 阅读 n 和 d

    • 创建一个向量并首先读入 d 数字

    • 读入其余数字并立即输出

    • 输出向量中的数字

    这就是全部，我认为你不能比完全省略工作更有效率;-)

    回复于

相关问题