优化C++数组旋转代码的时间复杂度 适配大输入规模

原代码核心问题 #

原代码采用逐位右移的实现逻辑，每旋转1次就要遍历整个数组挪动元素，时间复杂度为O(nr)*。结合题目约束n最大1e5、r最大1e6，最坏场景下单测试用例的操作量可达1e11量级，完全无法通过时间限制；同时原代码使用非标准的变长栈数组存储元素，大尺寸下存在栈溢出风险，且内外层循环重名变量容易引发边界错误。

优化核心逻辑 #

• 消除无效旋转步数：数组每旋转n次就会回到初始状态，因此实际需要的有效旋转步数可通过k = r % n直接计算，哪怕r取值达到1e6，有效步数最多也不超过n-1，直接消除r对时间复杂度的影响。
• 采用三次反转法实现旋转：仅用O(1)的额外空间，通过三次数组反转完成右旋转，整体时间复杂度为O(n)，无逐位移动的冗余操作。对应右旋转k步的操作流程为：
  1. 反转整个数组
  2. 反转数组前k个元素
  3. 反转数组后n-k个元素
     拿题目示例验证：数组[1,2,3,4,5]、右移2步，第一步全反转得[5,4,3,2,1]；第二步反转前2个得[4,5,3,2,1]；第三步反转后3个得[4,5,1,2,3]，和题目输出完全匹配。
• 适配大输入的存储与IO优化：使用标准动态容器vector存储数组元素，避免栈溢出；开启C++输入输出流的快速模式，降低大尺寸数据的IO耗时。

可运行优化代码 #

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
    // 开启快速IO，适配大输入规模
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    for(int case_idx = 0; case_idx < t; case_idx++){
        int n, r;
        cin >> n >> r;
        vector<int> a(n);
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
        // 计算有效旋转步数，消除无效冗余
        int k = r % n;
        // 三次反转法实现右旋转
        reverse(a.begin(), a.end());
        reverse(a.begin(), a.begin() + k);
        reverse(a.begin() + k, a.end());
        // 输出结果
        for(int i = 0; i < n; i++){
            cout << a[i] << " ";
        }
        cout << "\n";
    }
    return 0;
}

运行效果 #

原代码最坏场景单测试用例操作量约1e11，优化后单测试用例仅需3次遍历数组，操作量约3e5，在题目给定的约束下可以稳定运行无超时。

注：若旋转方向为左旋转，仅需调整三次反转的分段位置即可，核心思路不变。

内容的提问来源于stack exchange，提问作者Naveen Singla