56. 合并区间
2024-01-08 22:35:10
以数组?intervals
?表示若干个区间的集合,其中单个区间为?intervals[i] = [starti, endi]
?。请你合并所有重叠的区间,并返回?一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间?。
示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]] 输出:[[1,6],[8,10],[15,18]] 解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例?2:
输入:intervals = [[1,4],[4,5]] 输出:[[1,5]] 解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
二维数组排序:
// 先升序排序
Arrays.sort(intervals, (i1,i2) -> i1[0]-i2[0]);
方法1:(227ms)
public static int[][] merge(int[][] intervals) {
sort(intervals);
int[][] result = new int[intervals.length][2];
int index = 0;
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int[] interval : intervals) {
if (queue.size() == 0){
queue.addLast(interval[0]);
queue.addLast(interval[1]);
} else {
if (interval[0] <= queue.getLast()){
if (interval[1] > queue.getLast()){
queue.removeLast();
queue.addLast(interval[1]);
}
}else {
result[index][0] = queue.removeFirst();
result[index][1] = queue.removeLast();
index++;
queue.addLast(interval[0]);
queue.addLast(interval[1]);
}
}
}
result[index][0] = queue.getFirst();
result[index][1] = queue.getLast();
result = Arrays.copyOf(result, index + 1);
return result;
}
public static int[][] sort(int[][] srcArrays){
for (int i = 0; i < srcArrays.length - 1; i++) {
for (int j = i + 1; j < srcArrays.length; j++) {
if (srcArrays[i][0] > srcArrays[j][0]){
int temp[] = srcArrays[i];
srcArrays[i] = srcArrays[j];
srcArrays[j] = temp;
}
}
}
return srcArrays;
}
方法2:(0ms)
static int[][] merge(int[][] intervals) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int[] x : intervals) {
min = Math.min(min, x[0]);
max = Math.max(max, x[0]);
}
int[] range = new int[max - min + 1];
for (int i = 0; i < intervals.length; i++) {
// 记录了从某个start出发,最大结束区间是在哪里。即: range[start] = max(range[end])
range[intervals[i][0] - min] = Math.max(intervals[i][1] - min, range[intervals[i][0] - min]);
}
int start = 0;
int end = 0;
List<int[]> res = new ArrayList<>();
for (int i = 0; i < range.length; i++) {
if (range[i] == 0) {
// 没有从这个start出发的。
continue;
}
// 如果有,就计算这个点能到多远
if (i <= end) {
// 这个start在end以内,说明可以连接起来
end = Math.max(range[i], end);
} else {
// 这个satrt超出了end的范围,说明找到了一个区间。
res.add(new int[] { start + min, end + min });
start = i;
end = range[i];
}
}
res.add(new int[] { start + min, end + min });
return res.toArray(new int[res.size()][]);
}
方法3:(2ms)
public int[][] merge(int[][] intervals) {
quickSort(intervals,0,intervals.length-1);
List<int[]> ans = new ArrayList();
ans.add(intervals[0]);
for(int[] interval : intervals){
int[] ansInterval = ans.get(ans.size()-1);
if(ansInterval[1] < interval[0]){
ans.add(interval);
}else{
ansInterval[1] = Math.max(ansInterval[1],interval[1]);
}
}
return ans.toArray(new int[ans.size()][]);
}
方法4:(8ms)
public int[][] merge(int[][] intervals) {
// 先按照区间起始位置排序
Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
// 遍历区间
int[][] res = new int[intervals.length][2];
int idx = -1;
for (int[] interval: intervals) {
// 如果结果数组是空的,或者当前区间的起始位置 > 结果数组中最后区间的终止位置,
// 则不合并,直接将当前区间加入结果数组。
if (idx == -1 || interval[0] > res[idx][1]) {
res[++idx] = interval;
} else {
// 反之将当前区间合并至结果数组的最后区间
res[idx][1] = Math.max(res[idx][1], interval[1]);
}
}
return Arrays.copyOf(res, idx + 1);
}
作者:Sweetiee 🍬
链接:https://leetcode.cn/problems/merge-intervals/solutions/204805/chi-jing-ran-yi-yan-miao-dong-by-sweetiee/
方法5(9ms)
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> ans = new ArrayList<>();
for (int i = 0; i < intervals.length; ++i) {
if (ans.size() == 0 || intervals[i][0] > ans.get(ans.size() - 1)[1]) ans.add(intervals[i]);
else ans.get(ans.size() - 1)[1] = Math.max(intervals[i][1], ans.get(ans.size() - 1)[1]);
}
return ans.toArray(new int[ans.size()][2]);
}
文章来源:https://blog.csdn.net/linping_wong/article/details/135466741
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!