有偿看算法题

5.编程实现如下功能,要求时间复杂度为O(n)
在同一个时间,有很多人在出价买股票,一个典型的出价委托是这样的[buy/sell,price,unit]
一个有效的撮合是存在一对组合,其有效的unit>0,且buy价>sell价,此时以sell价作为成交价
现在要实时计算出当前的成交价,当前的成交价P应该满足如下条件在
P价以上的买方buy的单元数(unit之和)> P价以下(含)的卖方sell的单元数(unit之和)
P价以下的所有组合均可满足,优先满足最低Sell(卖出)价
可以想到,P的可能组合很多,当前需要快速计算出最大的P(此时称为成交价P_有效),即P+0.01时,就存在一个sell价=P的出价,其unit不能全部满足
给出N(N~10^8)组数据,如下
[buy, price, unit]
求P_有效
已知交易所对速度要求极高,因此时间复杂度要求远高于空间.

第5题本质上是个股票交易成交判定逻辑,输入
一组买的请求,数量+价格
一组卖的请求,数量+价格

当买的价格>=卖的价格时,可成交。
那么求当前的N个输入,在可成交的数量最大的前提下,最高可成交的价格是多少。
当买的价格>=卖的价格时,可成交。
那么求当前的N个输入,在可成交的数量最大的前提下,最高可成交的价格是多少。这个是提示
测试用例为
操作 价格 数量 
买 11 100 
买 10 100 
买 9 100 
卖 8 100 
卖 7 100 
成交价为卖的价格
当买的价格>=卖的价格时,可成交
即:买价格为11时候11*100>卖的价格 7*100 成交
买价格为11时候11*100>卖的价格 8*100 成交
所以最大成交价格为8。
操作 价格 数量 
卖 5 100 
买 10 100 
买 9 100 
卖 8 1000 
卖 7 1000 
关于用例1正确
关于用例2,买9覆盖卖5,买9、买10覆盖卖7的一部分,即当前实际可成交的部分为   卖5 100全部卖出,卖7 1000实际成交100,剩900未成交。即,当前实时价格应该为 7
有人能给个思路吗 如何时间复杂度为O(n)啊
全部评论
使用基数排序,时间复杂度能到on,排完序处理
1
送花
回复
分享
发布于 03-25 08:10 香港

相关推荐

1. 笔试环节(60min)笔试+讲解思路   一、     给出 k 种**不同面值**的硬币(以数组 coins 表示),每种面值硬币的数量**不限**。给出一个总金额 total,请算出最少需要几枚硬币可以凑出这个金额。如果凑不出则返回 -1。   *************************************************ion/?envType=study-plan-v2&envId=top-100-liked   二、     运用你所掌握的数据结构,设计和实现一个 LRU(Least Recently Used)缓存   三、     你正在设计一个类似 webpack 或 rollup 的打包工具,将页面的入口和所有依赖打包成一个文件。例如:页面 page 的主函数入口在page.js,以下为其通过 require 生成的依赖树。2. 自我介绍(10min)3. 简历提问(10min)   1. 在实习的时候有没有遇到什么性能上的问题,比如页面加载慢,你是怎么解决的?   2. 在实习的时候遇到的最大的困难是什么,你是怎么解决的?样式的调整   3. 实习的工作能不能详细说明一下,你们的研究有什么优势吗4. 技术提问   1. 进程、协程和线程,举例说明   2. webworker有使用过吗?   3. 说一下浏览器的缓存有几种方式,协商缓存强缓存介绍一下   4. settimeout会有不准的情况吗? 为什么5. 其他提问   1. 学校的学习是怎么样的,什么安排6. 反问环节   1. 面试官的工作方向(小程序,运行时)   2. 实习是需要6个月才可以转正吗问题:1. ts写算法题,需要配置一下2. 项目内容多准备准备#前端面经#
点赞 评论 收藏
转发
点赞 1 评论
分享
牛客网
牛客企业服务