57. 插入区间

wuchangjian2021-11-14 20:41:04编程学习

给你一个 无重叠的 ,按照区间起始端点排序的区间列表。

在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

我的思路:先新建个列表,将新区间按照左端递增的顺序插入进去,然后再按照56合并区间的方法进行合并即可

代码如下:

public class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int index = 0;//第一个比newInterval[0]大的索引
        while (index < intervals.length){
            if (newInterval[0] < intervals[index][0]){
                break;
            }
            res.add(intervals[index]);
            index++;
        }
        res.add(newInterval);
        for (int i = index; i < intervals.length; i++) {
            res.add(intervals[i]);
        }
        int[][] resArr = res.toArray(new int[res.size()][]);
        List<int[]> answer = new ArrayList<>();
        for (int i = 0; i < resArr.length; i++) {
            int L = resArr[i][0];
            int R = resArr[i][1];
            if (answer.isEmpty()){
                answer.add(new int[]{L,R});
            }else{
                int[] lastArr = answer.get(answer.size() - 1);
                if (L <= lastArr[1]){
                    lastArr[1] = Math.max(R,lastArr[1]);
                }else {
                    answer.add(new int[]{L,R});
                }
            }
        }
        return answer.toArray(new int[answer.size()][]);
    }
}

官方给出的思路是:

代码如下:

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        boolean placed = false;
        List<int[]> ansList = new ArrayList<int[]>();
        for (int[] interval : intervals) {
            if (interval[0] > right) {
                // 在插入区间的右侧且无交集
                if (!placed) {
                    ansList.add(new int[]{left, right});
                    placed = true;                    
                }
                ansList.add(interval);
            } else if (interval[1] < left) {
                // 在插入区间的左侧且无交集
                ansList.add(interval);
            } else {
                // 与插入区间有交集,计算它们的并集
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        if (!placed) {
            ansList.add(new int[]{left, right});
        }
        int[][] ans = new int[ansList.size()][2];
        for (int i = 0; i < ansList.size(); ++i) {
            ans[i] = ansList.get(i);
        }
        return ans;
    }
}

 

相关文章

测试总结.

一、什么是软件测试?(软件测试的定义)  ...

统计学习基础——第五章 重抽样

  目录 一、重抽样 1、概念 2、用途 3、缺点 4、方法 二、交叉验证...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。