第三代半导体 leetcodeLCP 矿工文档 xaml parsing join javafx gwt timer ansible datagrid jackson 河南网络推广 jquery清除子元素 axure组件库下载 java数据分析 windows查看进程命令 python数据类型转换 ln函数图像 kubernetes视频 react python正则提取字符串 python中index的用法 java接口 java操作mysql java时间格式化 java常用数据结构 java字符比较 linux系统安装教程图解 战地女记者 asp建站系统 亚索刀光特效包 苹果滚动截屏 c语言程序100例 电脑密码查看器 黑市商人 0x00000057 小米8游戏模式 1500左右性价比最高的手机 主播音效
当前位置: 首页 > 学习教程  > 编程语言

Leetcode 659. 分割数组为连续子序列(贪心)

2020/12/5 10:32:58 文章标签:

Description Solution 分割出来的子序列需要尽可能的长,所以我们对于每个数,都贪心的放入目前放入的最短的子序列即可 采用离散化优先队列实现 时间复杂度O(N∗log⁡N)O(N* \log N)O(N∗logN) Code class Solution { public:int mp[3*10007];priorit…

Description
在这里插入图片描述
Solution
分割出来的子序列需要尽可能的长,所以我们对于每个数,都贪心的放入目前放入的最短的子序列即可
采用离散化+优先队列实现

时间复杂度 O ( N ∗ log ⁡ N ) O(N* \log N) O(NlogN)

Code

class Solution {
public:
    int mp[3*10007];
    priority_queue<int,vector<int>,greater<int> >q[3*10007];
    bool isPossible(vector<int>& nums) {
        int sz = nums.size(), tot = 0, res = 0;
        for(int i = 0;i < sz;++i) {
            mp[++tot] = nums[i];
            mp[++tot] = nums[i]+1;
            mp[++tot] = nums[i]-1;
        }
        sort(mp+1,mp+1+tot);
        tot = unique(mp+1,mp+1+tot) - mp - 1;
        for(int i = 0;i < sz;++i) {
            int x = nums[i];
            int pos = lower_bound(mp+1,mp+1+tot,x) - mp;
            if(q[pos-1].size() == 0) {
                q[pos].push(1);
                res++;
            }else {
                int cnt = q[pos-1].top();q[pos-1].pop();
                if(cnt < 3) res--;
                q[pos].push(cnt+1);
                if(cnt + 1 < 3) res++;
            }
        }return res==0;
    }
};

本文链接: http://www.dtmao.cc/news_show_450246.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?