LeetCode 力扣官方题解 | 436. 寻找右区间

news/2024/10/30 9:33:11/

LeetCode 力扣官方题解 | 436. 寻找右区间

  1. 寻找右区间

题目描述

难易度:中等

给你一个区间数组 intervals ,其中 intervals [i] = [starti, endi] ,且每个 starti 都 不同 。

区间 i 的 右侧区间 可以记作区间 j ,并满足 startj >= endi ,且 startj 最小化 。

返回一个由每个区间 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 x 104
intervals[i].length == 2
-10
6 <= starti <= endi <= 10*6
每个间隔的起点都 不相同

解决方案

方法一:二分查找

思路和算法

最简单的解决方案是对于集合中的每个区间,我们扫描所有区间找到其起点大于当前区间的终点的区间(具有最小差值),时间复杂度为 O(n*2) ,在此我们不详细描述。

首先我们可以对区间 intervals 的起始位置进行排序,并将每个起始位置 intervals [i] [0] 对应的索引 i 存储在数组 startIntervals 中,然后枚举每个区间 i 的右端点 intervals [i] [1] ,利用二分查找来找到大于等于 intervals [i] [1] 的最小值 val 即可,此时区间 i 对应的右侧区间即为右端点 val 对应的索引。

代码

Python3

class Solution:def findRightInterval(self, intervals: List[List[int]]) -> List[int]:for i, interval in enumerate(intervals):interval.append(i)intervals.sort()n = len(intervals)ans = [-1] * nfor _, end, id in intervals:i = bisect_left(intervals, [end])if i < n:ans[id] = intervals[i][2]return ans

Java

class Solution {public int[] findRightInterval(int[][] intervals) {int n = intervals.length;int[][] startIntervals = new int[n][2];for (int i = 0; i < n; i++) {startIntervals[i][0] = intervals[i][0];startIntervals[i][1] = i;}Arrays.sort(startIntervals, (o1, o2) -> o1[0] - o2[0]);int[] ans = new int[n];for (int i = 0; i < n; i++) {int left = 0;int right = n - 1;int target = -1;while (left <= right) {int mid = (left + right) / 2;if (startIntervals[mid][0] >= intervals[i][1]) {target = startIntervals[mid][1];right = mid - 1;} else {left = mid + 1;}}ans[i] = target;}return ans;}
}

C++

class Solution {
public:vector<int> findRightInterval(vector<vector<int>>& intervals) {vector<pair<int, int>> startIntervals;int n = intervals.size();for (int i = 0; i < n; i++) {startIntervals.emplace_back(intervals[i][0], i);}sort(startIntervals.begin(), startIntervals.end());vector<int> ans(n, -1);for (int i = 0; i < n; i++) {auto it = lower_bound(startIntervals.begin(), startIntervals.end(), make_pair(intervals[i][1], 0));if (it != startIntervals.end()) {ans[i] = it->second;}}return ans;}
};

C#

public class Solution {public int[] FindRightInterval(int[][] intervals) {int n = intervals.Length;int[][] startIntervals = new int[n][];for (int i = 0; i < n; i++) {startIntervals[i] = new int[2];startIntervals[i][0] = intervals[i][0];startIntervals[i][1] = i;}Array.Sort(startIntervals, (o1, o2) => o1[0] - o2[0]);int[] ans = new int[n];for (int i = 0; i < n; i++) {int left = 0;int right = n - 1;int target = -1;while (left <= right) {int mid = (left + right) / 2;if (startIntervals[mid][0] >= intervals[i][1]) {target = startIntervals[mid][1];right = mid - 1;} else {left = mid + 1;}}ans[i] = target;}return ans;}
}

C


typedef struct {int start;int index;
} Node;int cmp(const void *pa, const void *pb) {return ((Node *)pa)->start - ((Node *)pb)->start;
}int* findRightInterval(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize) {Node * startIntervals = (Node *)malloc(sizeof(Node) * intervalsSize);for (int i = 0; i < intervalsSize; i++) {startIntervals[i].start = intervals[i][0];startIntervals[i].index = i;}qsort(startIntervals, intervalsSize, sizeof(Node), cmp);int * ans = (int *)malloc(sizeof(int) * intervalsSize);for (int i = 0; i < intervalsSize; i++) {int left = 0;int right = intervalsSize - 1;int target = -1;while (left <= right) {int mid = (left + right) / 2;if (startIntervals[mid].start >= intervals[i][1]) {target = startIntervals[mid].index;right = mid - 1;} else {left = mid + 1;}}ans[i] = target;}*returnSize = intervalsSize;return ans;
}

Golang


func findRightInterval(intervals [][]int) []int {for i := range intervals {intervals[i] = append(intervals[i], i)}sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })n := len(intervals)ans := make([]int, n)for _, p := range intervals {i := sort.Search(n, func(i int) bool { return intervals[i][0] >= p[1] })if i < n {ans[p[2]] = intervals[i][2]} else {ans[p[2]] = -1}}return ans
}

JavaScript

var findRightInterval = function(intervals) {const n = intervals.length;const startIntervals = new Array(n).fill(0).map(() => new Array(2).fill(0));for (let i = 0; i < n; i++) {startIntervals[i][0] = intervals[i][0];startIntervals[i][1] = i;}startIntervals.sort((o1, o2) => o1[0] - o2[0]);const ans = new Array(n).fill(0);for (let i = 0; i < n; i++) {let left = 0;let right = n - 1;let target = -1;while (left <= right) {const mid = Math.floor((left + right) / 2);if (startIntervals[mid][0] >= intervals[i][1]) {target = startIntervals[mid][1];right = mid - 1;} else {left = mid + 1;}}ans[i] = target;}return ans;
};

复杂度分析

时间复杂度:O(nlogn),其中 n 为区间数组的长度。排序的时间为 O(nlogn),每次进行二分查找花费的时间为 O(logn),一共需要进行 n 次二分查找,因此总的时间复杂度为 O(nlogn)。

空间复杂度:O(n),其中 n 为区间数组的长度。startIntervals 一共存储了 n 个元素,因此空间复杂度为 O(n)。

方法二:双指针

思路和算法

我们可以开辟两个新的数组:

startIntervals ,基于所有区间的起始点从小到大排序。
endIntervals ,基于所有区间的结束点从小到大排序。
我们从 endIntervals 数组中取出第 i 个区间,就可以从左到右扫描 startIntervals 数组中的区间起点来找到满足右区间条件的区间。

设 endIntervals 数组中第 i 个元素的右区间为 startIntervals 数组中的第 j 个元素,此时可以知道:startIntervals [j−1] [0] < endIntervals [i] [0] ,startIntervals [j] [0] ≥ endIntervals [i] [0] 。
当我们遍历 endIntervals 数组中第 i+1 个元素时,我们不需要从第一个索引开始扫描 startIntervals 数组,可以直接从第 j 个元素开始扫描 startIntervals 数组。
由于数组中所有的元素都是已排序,因此可以知道 startIntervals [j−1] [0] < endIntervals [i] [0] ≤ endIntervals [i+1] [0] 。
所以数组 startIntervals 的前 j−1 的元素的起始点都小于 endIntervals [i+1] [0] ,因此可以直接跳过前 j−1 个元素,只需要从 j 开始搜索即可。

代码

Python3

class Solution:def findRightInterval(self, intervals: List[List[int]]) -> List[int]:n = len(intervals)starts, ends = list(zip(*intervals))starts = sorted(zip(starts, range(n)))ends = sorted(zip(ends, range(n)))ans, j = [-1] * n, 0for end, id in ends:while j < n and starts[j][0] < end:j += 1if j < n:ans[id] = starts[j][1]return ans

Java

class Solution {public int[] findRightInterval(int[][] intervals) {int n = intervals.length;int[][] startIntervals = new int[n][2];int[][] endIntervals = new int[n][2];for (int i = 0; i < n; i++) {startIntervals[i][0] = intervals[i][0];startIntervals[i][1] = i;endIntervals[i][0] = intervals[i][1];endIntervals[i][1] = i;}Arrays.sort(startIntervals, (o1, o2) -> o1[0] - o2[0]);Arrays.sort(endIntervals, (o1, o2) -> o1[0] - o2[0]);int[] ans = new int[n];for (int i = 0, j = 0; i < n; i++) {while (j < n && endIntervals[i][0] > startIntervals[j][0]) {j++;}if (j < n) {ans[endIntervals[i][1]] = startIntervals[j][1];} else {ans[endIntervals[i][1]] = -1;}}return ans;}
}

C++

class Solution {
public:vector<int> findRightInterval(vector<vector<int>>& intervals) {vector<pair<int, int>> startIntervals;vector<pair<int, 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());vector<int> 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;}
};

C#

public class Solution {public int[] FindRightInterval(int[][] intervals) {int n = intervals.Length;int[][] startIntervals = new int[n][];int[][] endIntervals = new int[n][];for (int i = 0; i < n; i++) {startIntervals[i] = new int[2];startIntervals[i][0] = intervals[i][0];startIntervals[i][1] = i;endIntervals[i] = new int[2];endIntervals[i][0] = intervals[i][1];endIntervals[i][1] = i;}Array.Sort(startIntervals, (o1, o2) => o1[0] - o2[0]);Array.Sort(endIntervals, (o1, o2) => o1[0] - o2[0]);int[] ans = new int[n];for (int i = 0, j = 0; i < n; i++) {while (j < n && endIntervals[i][0] > startIntervals[j][0]) {j++;}if (j < n) {ans[endIntervals[i][1]] = startIntervals[j][1];} else {ans[endIntervals[i][1]] = -1;}}return ans;}
}

C

typedef struct {int start;int index;
} Node;int cmp(const void *pa, const void *pb) {return ((Node *)pa)->start - ((Node *)pb)->start;
}int* findRightInterval(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize){Node * startIntervals = (Node *)malloc(sizeof(Node) * intervalsSize);Node * endIntervals = (Node *)malloc(sizeof(Node) * intervalsSize);for (int i = 0; i < intervalsSize; i++) {startIntervals[i].start = intervals[i][0];startIntervals[i].index = i;endIntervals[i].start = intervals[i][1];endIntervals[i].index = i;}qsort(startIntervals, intervalsSize, sizeof(Node), cmp);qsort(endIntervals, intervalsSize, sizeof(Node), cmp);int * ans = (int *)malloc(sizeof(int) * intervalsSize);for (int i = 0, j = 0; i < intervalsSize; i++) {while (j < intervalsSize && endIntervals[i].start > startIntervals[j].start) {j++;}if (j < intervalsSize) {ans[endIntervals[i].index] = startIntervals[j].index;} else {ans[endIntervals[i].index] = -1;}}*returnSize = intervalsSize;free(startIntervals);free(endIntervals);return ans;
}

Golang

func findRightInterval(intervals [][]int) []int {n := len(intervals)type pair struct{ x, i int }starts := make([]pair, n)ends := make([]pair, n)for i, p := range intervals {starts[i] = pair{p[0], i}ends[i] = pair{p[1], i}}sort.Slice(starts, func(i, j int) bool { return starts[i].x < starts[j].x })sort.Slice(ends, func(i, j int) bool { return ends[i].x < ends[j].x })ans := make([]int, n)j := 0for _, p := range ends {for j < n && starts[j].x < p.x {j++}if j < n {ans[p.i] = starts[j].i} else {ans[p.i] = -1}}return ans
}

JavaScript

var findRightInterval = function(intervals) {const n = intervals.length;const startIntervals = new Array(n).fill(0).map(() => new Array(2).fill(0));const endIntervals = new Array(n).fill(0).map(() => new Array(2).fill(0));for (let i = 0; i < n; i++) {startIntervals[i][0] = intervals[i][0];startIntervals[i][1] = i;endIntervals[i][0] = intervals[i][1];endIntervals[i][1] = i;}startIntervals.sort((o1, o2) => o1[0] - o2[0]);endIntervals.sort((o1, o2) => o1[0] - o2[0]);const ans = new Array(n).fill(0);for (let i = 0, j = 0; i < n; i++) {while (j < n && endIntervals[i][0] > startIntervals[j][0]) {j++;}if (j < n) {ans[endIntervals[i][1]] = startIntervals[j][1];} else {ans[endIntervals[i][1]] = -1;}}return ans;
};

复杂度分析

时间复杂度:O(nlogn),其中 n 为区间数组的长度。两个数组的排序时间一共为 O(nlogn),查找每个区间的右侧区间的时间复杂度为 O(n),因此总的时间复杂度为 O(nlogn)。

空间复杂度:O(n),其中 n 为区间数组的长度。startIntervals , endIntervals 均存储了 n 个元素,因此空间复杂度为 O(n)。

获取更多详情:LeetCode 力扣官方题解 | 436. 寻找右区间
编辑/版式:pingping


http://www.ppmy.cn/news/271324.html

相关文章

技巧:win10的另一种美化字体的方式,使用noMeiryoUI

目录 1. 前提2. 字体选择3. 查看已经安装的字体并查看效果4. 安装软件修改系统字体5. 修改浏览器字体 1. 前提 21年的时候写了一篇文章&#xff0c;《Windows10下美化字体&#xff0c;达到类似mac的效果》&#xff0c;当时还很迷恋macType这个软件的使用&#xff0c;觉得好牛逼…

某电机修造厂变电所一次系统设计

摘要 由于国内人民生活水平的提高&#xff0c;科技不断地进步&#xff0c;控制不断地完善&#xff0c;从而促使变电所设计技术在电气系统领域占据主导权&#xff0c;也使得110kV变电所被广泛应用。在变电所系统设计领域中&#xff0c;110kV变电所成为目前一处亮丽的风景线&…

酷睿i513400参数 i5 13400功耗 i5 13400属于什么水平档次级别

i5-13400 CPU 拥有 6 个大核和 4 个小核&#xff0c;共计 10 核 16 线程&#xff0c;主频 2.5 GHz&#xff0c;全核睿频可达 4.1 GHz&#xff0c;单核睿频 4.6 GHz&#xff0c;配备 28 MB 的 L3 缓存&#xff0c;基础功耗 65W。 i513400组装电脑怎么搭配更合适这些点很重要 htt…

i513400f和i512400f差距 i5 13400f和i5 12400f区别对比

i512400f是6核12线程&#xff0c;默认主频2.5GHz&#xff0c;单核最大加速频率4.4GHz&#xff0c;全核最大加速频率4.0GHz&#xff0c;不支持超频&#xff0c;二级缓存7.5MB 三级缓存为18MB&#xff0c;内存支持DDR5-4800/DDR4-3200&#xff0c;TDP功耗为65W. 组装电脑选i5 124…

1078 字符串压缩与解压 (20 分) (C语言)

文本压缩有很多种方法&#xff0c;这里我们只考虑最简单的一种&#xff1a;把由相同字符组成的一个连续的片段用这个字符和片段中含有这个字符的个数来表示。例如 ccccc 就用 5c 来表示。如果字符没有重复&#xff0c;就原样输出。例如 aba 压缩后仍然是 aba。 解压方法就是反…

PTA 1078 字符串压缩与解压(Python3)

文本压缩有很多种方法&#xff0c;这里我们只考虑最简单的一种&#xff1a;把由相同字符组成的一个连续的片段用这个字符和片段中含有这个字符的个数来表示。例如 ccccc 就用 5c 来表示。如果字符没有重复&#xff0c;就原样输出。例如 aba 压缩后仍然是 aba。 解压方法就是反…

【项目】树莓派4B镜像安装

本文主要记录下如何使用Raspberry Pi image 软件进行树莓派镜像进行安装。 官网&#xff1a;Raspberry Pi OS – Raspberry Pi 百度网盘&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1G7z1Fdvk5Chmhj894WPU3A 提取码&#xff1a;xnzw 一、格式化SD卡 若SD卡存在…

酷睿i5 12490f什么水平 i5 12490f属于什么档次 i512490f怎么样

i5-12490F可以看做是i5-12400F的加强版&#xff0c;最显眼的变化就是频率从2.5GHz&#xff5e;4.4GHz提升到3.0GHz&#xff5e;4.6GHz&#xff0c;其他看似差不多。价格随有波动&#xff0c;但基本保持在比i5-12400贵100元的水平。当然比高一级的i5-12600KF要便宜得多啦。i5 12…