《算法设计与分析》循环右移合并数组

1001-高同学

发表文章数:265

首页 » LeetCode » 正文

题目:有已经排好序的数组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;
}

 

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《《算法设计与分析》循环右移合并数组》 发布于2018-09-24

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录