408-数据结构-两个线性表互换位置

王道书习题2.2.3 应用题07

题目：已知一维数组A[m+n]中依次存放两个线性表(a1,a2,a3…am)和(b1,b2,b3…bn).编写一个函数，将数组中的两个顺序表位置互换，既将(a1,a2,a3…am)放在(b1,b2,b3…bn)前面

最开始想到的是循环左移m位。

void twoListReverse(vector<int>& arr,int m ,int n){
    //循环左移m位
    int temp = arr[0];
    for (int i = 0; i <m; ++i) {
        for (int j = 1; j < arr.size(); ++j) {
            arr[j-1] = arr[j];
        }
        arr[arr.size()-1] = temp;
        temp = arr[0];
    }
}

时间复杂度O(nm)

解法二：

首先将A[m+n]中的全部元素(a1,a2,a3…am,b1,b2,b3…bn)原地逆置，(bn,b(n-1),…b1,am,a(m-1),…a1);最后分别对前n个元素和后m个元素使用逆置算法，既得(b1,b2,b3…bn,a1,a2,a3…am)

void Reverse(vector<int>& arr,int left ,int right){
    if (left>=right  right >= arr.size()){
        return;
    }
    int mid = (left+right)>>1;
    for (int i = 0; i <= mid-left; ++i) {
        int temp = arr[left+i];
        arr[left+i] = arr[right-i];
        arr[right-i] = temp;
    }
}

void Exchange(vector<int>& arr,int m ,int n){
    Reverse(arr,0,m+n-1);
    Reverse(arr,0,n-1);
    Reverse(arr,n,m+n-1);
}

时间复杂度O(n)