减少下面给定代码的时间复杂度。代码工作正常问题是时间复杂度

Question

/*第一行将包含一个整数T，表示测试用例的数量。对于每个测试用例：

第一行由两个整数n和r组成，n为数组元素个数，r为旋转步数
下一行由N个space分隔的整数组成，表示数组a的元素。

限制条件：

1<=t<=20

1<=n<=10^5

0<=k<=10^6

0<=a[i]<=10^6

输入

1

5 2

1 2 3 4 5 6

输出

4 5 1 2 3 */

//我的代码

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

int main(){
   
    int t,n,r;
    cin>>t;
    
    for (int i = 0; i < t; i++)
    {
        cin >> n >> r;                    // inputting number of element in array and number of rotation
        int a[n];
        for (int i = 0; i < n; i++)
        {
            cin>>a[i];                                           //taking input from user in array
        }
        n--;
        for (int i = 0; i < r; i++)
        {
            n++;
            for (int i = n; i >= 0; i--)
            {
                a[i]=a[i-1];
            }                                    // help me to improve this inner loop and add a little bit 
            a[0]=a[n];                           //of explanation for your logic and pls give answer in c++
            n--; 
        }
        for (int i = 0; i <= n; i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}

Answer 1

您的代码中有一处非标准用法：

    int a[n];

尽管被 gcc 接受为扩展，VLA are not part of C++

现在回答您的问题：不是一次移动数组的所有元素，而是一次移动一次，只需注意您应该只移动一次 r%n 步。这将大大降低时间复杂度，但您将不得不分配第二个数组：

...
int *a = new int[n];
int *result = new int[n];
...
r %= n;
for (int i=0; i<n; i++) {
    result[(i + r) % n] = a[i];
}
...

减少下面给定代码的时间复杂度。代码工作正常问题是时间复杂度

reduce the time complexity of below given code .The code working fine the problem is time complexity

c++

arrays

time-complexity