c++ - 超过 Hackerrank 的时间限制

Question

我成功解决了一个关于 Hackerrank 的问题，它通过了所有测试用例，但我得到了一个错误，超过了时间限制。我猜如果我优化我的代码它会工作，但我想不出任何方法来使我的代码更有效率。

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

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

谁能指导我如何使这段代码更有效率？

我的代码是:

vector<int> array_left_rotation(vector<int> a, int n, int k) {
    for (int j = 0; j < k; j++){
        a[n] = a[0];
        for (int i = 0; i < n; i++){
            a[i] = a[i+1];
        }
        a[n-1] = a[n];
    }
    return a;
}

n 是数组中元素的个数k是要执行的旋转数

Answer 1

对于这个问题，您不需要实际旋转数组。公式 (i + k) % n 将为您提供已向左旋转 k 次的数组中索引为 i 的元素.知道这一点后，您可以通过这种方式访问​​每个元素来遍历数组:

int main() {
  int* arr, n, k, i;
  cin >> n >> k;
  arr = new int[n];
  for (i = 0; i < n; ++i)
    cin >> arr[i];
  for (i = 0; i < n; ++i)
    cout << arr[(i + k) % n] << " ";
}