最长单调子序列 复杂度nlog(n)

//最长单调子序列 复杂度nlog(n)
//参数(原序列,序列长度,生成的序列),传入序列长度必须大于0
//返回值中lengthRecord中前k项表示长度为k的最小字序列
//LIScmp为关系函数,原函数表明lengthRecord为递增(不含等于)
typedef double LISTYPE;
#define LISMAXN 10000
int LIScmp(LISTYPE a,LISTYPE b)
{
    return a < b;
}
long LISLength(LISTYPE list[],long n,LISTYPE lengthRecord[])
{
    long length = 1,lth;
    LISTYPE lR[LISMAXN];
    lR[0] = list[0];

    for(int i = 1 ; i < n ; i ++)
    {
        //二分查找,复杂度 log(n)
        int b,e,m;
        b = 0;
        e = length - 1;
        while(b <= e && e >= 0)
        {
            m = (b + e) / 2;
            if(LIScmp(lR[m],list[i]))
                b = m + 1;
            else
                e = m - 1;
        }
        lR[b] = list[i];
        if(b >= length)
            length ++;
    }
    /*
    *计算序列部分
    *复杂度nlog(n)
    */
    lth = 1;
    for(int i = 1 ; i < n ; i ++)
    {
        //二分查找,复杂度 log(n)
        int b,e,m;
        b = 0;
        e = lth - 1;
        while(b <= e && e >= 0)
        {
            m = (b + e) / 2;
            if(LIScmp(lR[m],list[i]))
                b = m + 1;
            else
                e = m - 1;
        }
        lR[b] = list[i];
        if(b >= lth)
            lth ++;
        if(lth == length)
        {
            for(b = 0 ; b < length ; b ++)
                lengthRecord[b] = lR[b];
            break;
        }
    }
    //计算序列部分代码与之前的类似,可以直接Copy然后修改
    return length;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

51 Nod 1791 合法括号子段【分治+字符串】

1791 合法括号子段 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题 有一个括号序列,现在要计算一下它有多少非空子段是合法...

30860
来自专栏静默虚空的博客

排序五 简单选择排序

要点 简单选择排序是一种选择排序。 选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。 简单排序处理流程 ...

21190
来自专栏漫漫深度学习路

pytorch学习笔记(十七):python 端扩展 pytorch

pytorch 虽然提供了很多的 op 使得我们很容易的使用。但是当已有的 op 无法满足我们的要求的时候,那就需要自己动手来扩展。 pytorch 提供了两种...

31070
来自专栏数据结构与算法

23:过滤多余的空格

23:过滤多余的空格 总时间限制: 1000ms 内存限制: 65536kB描述 一个句子中也许有多个连续空格,过滤掉多余的空格,只留下一个空格。 输入一...

35040
来自专栏分布式系统和大数据处理

正则表达式教程

11450
来自专栏书山有路勤为径

包含min函数的栈

LeetCode 155. Min Stack 设计一个栈,支持如下操作,这些操作的算法复杂度需要是常数级,O(1) 1.push(x) : 将元素x压入...

10710
来自专栏一直在跳坑然后爬坑

RxJava2操作符之“Scan”作用示例用法运行结果分析总结

扫描,遍历,用法和上一个Reduce操作符差不多,只是这个操作符会将每一个过程的中间产物发射出来,而不是只发射结果

10330
来自专栏Jed的技术阶梯

图解冒泡排序

在上面实现的代码中,即使n个数本来就是有序的,也会进行(n-1)次排序(只比较,不交换) 优化:当数组已经有序后,就中断循环

20730
来自专栏xingoo, 一个梦想做发明家的程序员

快速排序

算法思想:对于输入的子数组a[p:r],按下面三个步骤: 1 分解:以a[p]为基准元素将a[p:r]分成三段,a[p:q-1],a[q],a[q+1:r],使...

21790
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题31连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组和的最大值。要求时间复杂度为O(n) 分析:统计连续子数...

30790

扫码关注云+社区

领取腾讯云代金券