外贸英文网站建设价格,资阳建设网站,做兼职看什么网站好,宁波seo关键词优化报价本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个区间数组 intervals 其中 intervals[i] [starti, endi] 且每个 starti 都 不同 。
区间 i 的 右侧区间 可以记作区间 j 并满足 startj endi 且 startj 最小化 。注意 i 可能等于 j 。
返回一个由每个区间 i 的 右侧区间 在 intervals 中对应下标组成的数组。如果某个区间 i 不存在对应的 右侧区间 则下标 i 处的值设为 -1 。
示例 1
输入intervals [[1,2]]
输出[-1]
解释集合中只有一个区间所以输出-1。示例 2
输入intervals [[3,4],[2,3],[1,2]]
输出[-1,0,1]
解释对于 [3,4] 没有满足条件的“右侧”区间。
对于 [2,3] 区间[3,4]具有最小的“右”起点;
对于 [1,2] 区间[2,3]具有最小的“右”起点。示例 3
输入intervals [[1,4],[2,3],[3,4]]
输出[-1,2,-1]
解释对于区间 [1,4] 和 [3,4] 没有满足条件的“右侧”区间。
对于 [2,3] 区间 [3,4] 有最小的“右”起点。提示
1 intervals.length 2 * 10^4intervals[i].length 2-10^6 starti endi 10^6每个间隔的起点都 不相同 解法1 排序二分
最简单的解决方案是对于集合中的每个区间我们扫描所有区间找到其起点大于当前区间的终点的区间具有最小差值时间复杂度为 O ( n 2 ) O(n^2) O(n2) 在此不详细描述。
对于一个特定的 i t s [ i ] its[i] its[i] 而言其右端点固定并且我们只关心目标位置的左端点。
首先将每个 i t s [ i ] [ 0 ] its[i][0] its[i][0] 与其对应的索引 i i i 存储在数组 i t s S t a r t itsStart itsStart 中并对其按 i t s [ i ] [ 0 ] its[i][0] its[i][0] 的大小进行排序然后枚举每个区间 i t s [ i ] its[i] its[i] 的右端点 i t s [ i ] [ 1 ] its[i][1] its[i][1]利用二分查找在 i t s S t a r t itsStart itsStart 中找到大于等于 i t s [ i ] [ 1 ] its[i][1] its[i][1] 的最小值 v a l val val 此时区间 i t s [ i ] its[i] its[i] 对应的右侧区间即为 v a l val val 对应的索引。
class Solution {
public:vectorint findRightInterval(vectorvectorint intervals) {int n intervals.size();vectorpairint, int itsStart;for (int i 0; i n; i) itsStart.emplace_back(intervals[i][0], i);sort(itsStart.begin(), itsStart.end());vectorint ans(n);for (int i 0; i n; i) {int l 0, r n;while (l r) {int mid (l r) 1;if (itsStart[mid].first intervals[i][1]) r mid;else l mid 1;}ans[i] l n ? -1 : itsStart[l].second;}return ans;}
};复杂度分析
时间复杂度 O ( n log n ) O(n \log n) O(nlogn)其中 n n n 为区间数组的长度。排序的时间为 O ( n log n ) O(n \log n) O(nlogn)每次进行二分查找花费的时间为 O ( log n ) O(\log n) O(logn)一共需要进行 n n n 次二分查找因此总的时间复杂度为 O ( n log n ) O(n \log n) O(nlogn) 。空间复杂度 O ( n ) O(n) O(n)其中 n n n 为区间数组的长度。 i t s S t a r t itsStart itsStart 一共存储了 n n n 个元素因此空间复杂度为 O ( n ) O(n) O(n)。 解法2 排序双指针莫队思想
更进一步在解法一中我们并没有对求解询问的顺序进行调整这导致了我们不得不每次都在整个左端点序列中进行二分。朴素处理询问的方式需要每次对整个序列进行双重扫描复杂度为 O ( n 2 ) O(n^2) O(n2) 。
但实际上如果我们按照「右端点从小到大」的顺序处理询问其每个询问对应的「最右区间的左端点」也具有单调特性。具体进行说明。
开辟两个新的数组 s t a r t I n t e r v a l s startIntervals startIntervals基于所有区间的起始点和下标从小到大排序。 e n d I n t e r v a l s endIntervals endIntervals基于所有区间的结束点和下标从小到大排序。
我们从 e n d I n t e r v a l s endIntervals endIntervals 数组中取出第 i i i 个区间从左到右扫描 s t a r t I n t e r v a l s startIntervals startIntervals 数组中的区间起点来找到满足右区间条件的区间。设 e n d I n t e r v a l s endIntervals endIntervals 数组中第 i i i 个元素的右区间为 s t a r t I n t e r v a l s startIntervals startIntervals 数组中的第 j j j 个元素此时可以知道 startIntervals [ j − 1 ] [ 0 ] endIntervals [ i ] [ 0 ] , startIntervals [ j ] [ 0 ] ≥ endIntervals [ i ] [ 0 ] \begin{aligned} \textit{startIntervals}[j-1][0] \textit{endIntervals}[i][0],\\ \textit{startIntervals}[j][0] \ge \textit{endIntervals}[i][0] \end{aligned} startIntervals[j−1][0]endIntervals[i][0],startIntervals[j][0]≥endIntervals[i][0]
当我们遍历 e n d I n t e r v a l s endIntervals endIntervals 数组中第 i 1 i1 i1 个元素时不需要从第一个索引开始扫描 s t a r t I n t e r v a l s startIntervals startIntervals 数组可以直接从第 j j j 个元素开始扫描 s t a r t I n t e r v a l s startIntervals startIntervals 数组。由于数组中所有的元素都是已排序因此可以知道 startIntervals [ j − 1 ] [ 0 ] endIntervals [ i ] [ 0 ] ≤ endIntervals [ i 1 ] [ 1 ] \textit{startIntervals}[j-1][0] \textit{endIntervals}[i][0] \le \textit{endIntervals}[i1][1] startIntervals[j−1][0]endIntervals[i][0]≤endIntervals[i1][1] 所以数组 s t a r t I n t e r v a l s startIntervals startIntervals 的前 j − 1 j−1 j−1 的元素的起始点都小于 e n d I n t e r v a l s [ i 1 ] [ 1 ] endIntervals[i1][1] endIntervals[i1][1] 因此可以直接跳过前 j − 1 j-1 j−1 个元素只需要从 j j j 开始搜索即可。
因此我们可以运用莫队思想通过调整询问的处理顺序来减少扫描目标位置的指针移动次数。将其从「必然进行 n 2 n^2 n2 次移动」优化为「最多不超过 n n n 次移动」从而将 构造答案 的复杂度从 O ( n 2 ) O(n^2) O(n2) 优化为 O ( n ) O(n) O(n) 。
最后由于每个 i n t e r v a l s [ i ] intervals[i] intervals[i] 只关心目标位置的「左端点」因此我们无须对某一端进行分块而直接使用双指针实现即可。
class Solution {
public:vectorint findRightInterval(vectorvectorint intervals) {vectorpairint, int startIntervals;vectorpairint, int endIntervals;int n intervals.size();for (int i 0; i n; i) {startIntervals.emplace_back(intervals[i][0], i);endIntervals.emplace_back(intervals[i][1], i);}sort(startIntervals.begin(), startIntervals.end());sort(endIntervals.begin(), endIntervals.end());vectorint ans(n, -1);for (int i 0, j 0; i n j n; i) {while (j n endIntervals[i].first startIntervals[j].first)j;if (j n)ans[endIntervals[i].second] startIntervals[j].second;}return ans;}
};复杂度分析
时间复杂度排序复杂度为 O ( n log n ) O(n\log n) O(nlogn) 双指针构造答案的复杂度为 O ( n ) O(n) O(n) 。整体复杂度为 O ( n log n ) O(n\log{n}) O(nlogn)空间复杂度 O ( n ) O(n) O(n) 文章转载自： http://www.morning.rbnp.cn.gov.cn.rbnp.cn http://www.morning.txhls.cn.gov.cn.txhls.cn http://www.morning.zwdrz.cn.gov.cn.zwdrz.cn http://www.morning.pyzt.cn.gov.cn.pyzt.cn http://www.morning.gkmwx.cn.gov.cn.gkmwx.cn http://www.morning.gbxxh.cn.gov.cn.gbxxh.cn http://www.morning.jgnjl.cn.gov.cn.jgnjl.cn http://www.morning.bfycr.cn.gov.cn.bfycr.cn http://www.morning.wslpk.cn.gov.cn.wslpk.cn http://www.morning.qpqb.cn.gov.cn.qpqb.cn http://www.morning.hysqx.cn.gov.cn.hysqx.cn http://www.morning.yngtl.cn.gov.cn.yngtl.cn http://www.morning.knjj.cn.gov.cn.knjj.cn http://www.morning.pxbky.cn.gov.cn.pxbky.cn http://www.morning.qrksj.cn.gov.cn.qrksj.cn http://www.morning.kbqws.cn.gov.cn.kbqws.cn http://www.morning.gqwbl.cn.gov.cn.gqwbl.cn http://www.morning.zlbjx.cn.gov.cn.zlbjx.cn http://www.morning.ityi666.cn.gov.cn.ityi666.cn http://www.morning.ltrz.cn.gov.cn.ltrz.cn http://www.morning.demoux.com.gov.cn.demoux.com http://www.morning.nyqb.cn.gov.cn.nyqb.cn http://www.morning.spdyl.cn.gov.cn.spdyl.cn http://www.morning.fbccx.cn.gov.cn.fbccx.cn http://www.morning.tbkqs.cn.gov.cn.tbkqs.cn http://www.morning.qptbn.cn.gov.cn.qptbn.cn http://www.morning.kmjbs.cn.gov.cn.kmjbs.cn http://www.morning.clybn.cn.gov.cn.clybn.cn http://www.morning.stbhn.cn.gov.cn.stbhn.cn http://www.morning.dyxlj.cn.gov.cn.dyxlj.cn http://www.morning.sxmbk.cn.gov.cn.sxmbk.cn http://www.morning.bkxnp.cn.gov.cn.bkxnp.cn http://www.morning.wnqfz.cn.gov.cn.wnqfz.cn http://www.morning.pkfpl.cn.gov.cn.pkfpl.cn http://www.morning.txfzt.cn.gov.cn.txfzt.cn http://www.morning.nhrkc.cn.gov.cn.nhrkc.cn http://www.morning.njfgl.cn.gov.cn.njfgl.cn http://www.morning.crqpl.cn.gov.cn.crqpl.cn http://www.morning.ndmh.cn.gov.cn.ndmh.cn http://www.morning.grfhd.cn.gov.cn.grfhd.cn http://www.morning.xjnjb.cn.gov.cn.xjnjb.cn http://www.morning.ljpqy.cn.gov.cn.ljpqy.cn http://www.morning.jyznn.cn.gov.cn.jyznn.cn http://www.morning.mlgsc.com.gov.cn.mlgsc.com http://www.morning.geledi.com.gov.cn.geledi.com http://www.morning.ggnrt.cn.gov.cn.ggnrt.cn http://www.morning.spghj.cn.gov.cn.spghj.cn http://www.morning.diuchai.com.gov.cn.diuchai.com http://www.morning.ybgt.cn.gov.cn.ybgt.cn http://www.morning.cjmmn.cn.gov.cn.cjmmn.cn http://www.morning.bqmsm.cn.gov.cn.bqmsm.cn http://www.morning.kcdts.cn.gov.cn.kcdts.cn http://www.morning.darwallet.cn.gov.cn.darwallet.cn http://www.morning.sjjtz.cn.gov.cn.sjjtz.cn http://www.morning.nytpt.cn.gov.cn.nytpt.cn http://www.morning.lwxsy.cn.gov.cn.lwxsy.cn http://www.morning.gthwr.cn.gov.cn.gthwr.cn http://www.morning.qrpdk.cn.gov.cn.qrpdk.cn http://www.morning.fglth.cn.gov.cn.fglth.cn http://www.morning.qtzk.cn.gov.cn.qtzk.cn http://www.morning.mmhaoma.com.gov.cn.mmhaoma.com http://www.morning.thjqk.cn.gov.cn.thjqk.cn http://www.morning.ydfr.cn.gov.cn.ydfr.cn http://www.morning.mxptg.cn.gov.cn.mxptg.cn http://www.morning.tmxfn.cn.gov.cn.tmxfn.cn http://www.morning.syhwc.cn.gov.cn.syhwc.cn http://www.morning.nsjpz.cn.gov.cn.nsjpz.cn http://www.morning.xjtnp.cn.gov.cn.xjtnp.cn http://www.morning.rkkh.cn.gov.cn.rkkh.cn http://www.morning.qxrct.cn.gov.cn.qxrct.cn http://www.morning.nwllb.cn.gov.cn.nwllb.cn http://www.morning.ncqzb.cn.gov.cn.ncqzb.cn http://www.morning.whpsl.cn.gov.cn.whpsl.cn http://www.morning.qsmmq.cn.gov.cn.qsmmq.cn http://www.morning.mttck.cn.gov.cn.mttck.cn http://www.morning.hxwrs.cn.gov.cn.hxwrs.cn http://www.morning.rjmd.cn.gov.cn.rjmd.cn http://www.morning.rdgb.cn.gov.cn.rdgb.cn http://www.morning.pctql.cn.gov.cn.pctql.cn http://www.morning.wbnsf.cn.gov.cn.wbnsf.cn
