数组左移D位出现Segmentation Fault问题求助（附C++代码）

问题描述 #

需要实现数组向左（逆时针）旋转D个位置（D为正整数），采用O(N)时间复杂度的翻转法，小输入下代码正常，但处理大输入（如N=1e6）时出现Segmentation Fault。尝试用vector创建动态数组但驱动代码不允许，代码如下：

//{ Driver Code Starts
#include<bits/stdc++.h>
using namespace std;


// } Driver Code Ends
class Solution{
    public:
    
    //Function to rotate an array by d elements in counter-clockwise direction. 
    void reverse(int arr[], int low, int high)
        {
            while(low<high)
            {
                swap(arr[low], arr[high]);
                low++;
                high--;
            }
        }
    void rotateArr(int arr[], int d, int n){
        // code here
        
        reverse(arr,0,d-1);
        reverse(arr,d,n-1);
        reverse(arr,0,n-1);
    }
};

//{ Driver Code Starts.

int main() {
    int t;
    //taking testcases
    cin >> t;
    
    while(t--){
        int n, d;
        
        //input n and d
        cin >> n >> d;
        
        int arr[n];
        
        //inserting elements in the array
        for(int i = 0; i < n; i++){
            cin >> arr[i];
        }
        Solution ob;
        //calling rotateArr() function
        ob.rotateArr(arr, d,n);
        
        //printing the elements of the array
        for(int i =0;i<n;i++){
            cout << arr[i] << " ";
        }
        cout << endl;
    }
    return 0;
}
// } Driver Code Ends

问题根源 #

• 栈溢出：主函数里用int arr[n];定义的是变长数组，这类数组在栈上分配内存。栈的默认大小通常只有几MB，当N达到1e6时，数组所需内存（4MB~8MB）很容易超过栈的容量，直接触发栈溢出导致段错误。
• 下标越界：当D≥N时，reverse(arr,0,d-1)会访问arr[d-1]，如果D>N，d-1会超出数组的最大下标N-1，触发越界访问，同样导致段错误。

修复方案 #

1. 替换变长数组为堆内存分配 #

把栈上的变长数组换成new在堆上分配，堆的内存空间远大于栈，能轻松容纳1e6级别的数组：

// 替换原有的int arr[n];
int* arr = new int[n];
// 使用后记得释放内存，避免泄漏
delete[] arr;

2. 对D取模处理 #

旋转N次等于没旋转，先对D取模，确保D在0到N-1范围内，避免越界：

void rotateArr(int arr[], int d, int n){
    d = d % n;
    if(d == 0) return; // 无需旋转直接返回
    
    reverse(arr,0,d-1);
    reverse(arr,d,n-1);
    reverse(arr,0,n-1);
}

完整修复代码 #

//{ Driver Code Starts
#include<bits/stdc++.h>
using namespace std;


// } Driver Code Ends
class Solution{
    public:
    
    //Function to rotate an array by d elements in counter-clockwise direction. 
    void reverse(int arr[], int low, int high)
        {
            while(low<high)
            {
                swap(arr[low], arr[high]);
                low++;
                high--;
            }
        }
    void rotateArr(int arr[], int d, int n){
        d = d % n;
        if(d == 0) return;
        
        reverse(arr,0,d-1);
        reverse(arr,d,n-1);
        reverse(arr,0,n-1);
    }
};

//{ Driver Code Starts.

int main() {
    int t;
    cin >> t;
    
    while(t--){
        int n, d;
        cin >> n >> d;
        
        int* arr = new int[n];
        
        for(int i = 0; i < n; i++){
            cin >> arr[i];
        }
        Solution ob;
        ob.rotateArr(arr, d,n);
        
        for(int i =0;i<n;i++){
            cout << arr[i] << " ";
        }
        cout << endl;
        
        delete[] arr;
    }
    return 0;
}
// } Driver Code Ends

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