在黑客排名上超过时间限制

Question

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

问题是：对大小为n的数组进行左旋操作会将数组的每个元素向左移动1个单位。例如，如果在数组[1,2,3,4,5]上执行两次左旋转，则该数组将变为[3,4,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

如果另一个向量不会导致空间问题，您可以复制它们，但要有一个偏移量:

//Not tested
vector<int> array_left_rotation(vector<int> a, int n, int k) {
    std::vector<int> result(n);
    for (int j = 0; j < k; j++){
       result[j]=a[(j+k)%n];
    }
    return result;
}

Answer 2

不执行k旋转，而是尝试执行k旋转:一次将整个数组向左旋转k。那效率就高多了。

Answer 3

您不需要实际旋转数组来解决这个问题。公式（i k）%n将为您提供数组中索引i处的元素，该数组已向左旋转k次。了解这一点，您可以通过以下方式访问每个元素一次来遍历数组：

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] << " ";
}