题目：有已经排好序的数组arr[0:k-1]和arr[k:n-1]，现在将两个数组合并成一个大的有序数组。要求：时间复杂度最坏的情况下为0(n)，空间复杂的度为o(1)。

之前看过《算法笔记》上面将递归时，有个two pointers思想，讲的正好是怎么将两个有序数组在时间复杂度为O(n)的情况下合并成一个大的有序数组。但是这种思想所用到的空间复杂度为o(n)，本题中就不适用。

笔者的想法是选择arr[i:k-1]和arr[j:n-1]（初始时i=0，j=k）中最小的数，如果该数在arr[j:n-1]中，那么该数必定时arr[j]，交换arr[i]与arr[j]，则（如果）该数在arr[i:k-1]中，直接I++即可。这种想法，由于还要将arr[j:n-1]在进行排序，最坏情况下的时间复杂度相比于o(n)增加到o(nlogn)。笔者想不出了什么高效的算法，于是偷偷看解答书。?

《算法设计与分析习题解答》中提供了一种思想—–>循环右移数组方法。书中讲的这个方法的大概思想如下：在arr[0:k-1]中找出arr[i]（i范围是0~k-1）在arr[k:n-1]中的位置（二分查找法），记为pos，在计算pos到k的距离，则从i到pos一直往复循环，次数为距离。

代码如下可能不好懂，但一定要认真理解。

#include <bits/stdc++.h>

using namespace std;
//算法实现：用o(1)的空间复杂度，时间复杂度最坏为o(n)的情况下
//合并同一个数组的两个排好序的部分，将其变成一个大的有序数组
const int maxn = 1e5+10;
int arr[maxn];
int binarySearch(int x,int left,int right)
{
    int mid;
    while(left <= right)
    {
        mid = (right-left)/2+left;
        if(arr[mid] == x) return mid;
        if(arr[mid] > x) right = mid-1;
        else
            left = mid+1;
    }
    if(arr[mid] == x)
        return mid;
    else
        return mid-1;
}
void shiftRight(int k,int s,int e)  //k是移动次数，s是开始循环移动的地方，e是结束循环移动的地方
{
    for(int i=0; i<k; i++)
    {
        int tmp = arr[e];
        for(int j=e; j>s; j--)
            arr[j] = arr[j-1];
        arr[s] = tmp;
    }
}
void mer(int k,int n)
{
    int i=0,j=k;
    while(i<j && j<n)
    {
        int pos = binarySearch(arr[i],j,n-1);
        shiftRight(pos-j+1,i,pos);
        j = pos+1;
        i = i + pos - j +2;
    }
}
int main()
{
    int n,i,k;
    cin>>n;
    for(i=0; i<n; i++)
    {
        cin>>arr[i];
        if(arr[i] < arr[i-1])
        {
            k = i;
        }
    }
    mer(k,n);
    for(i=0; i<n; i++)
        cout<<arr[i]<<" ";
    return 0;
}

分享到：

赞(0) 打赏