C++如何插入區間

這篇文章主要介紹“C++如何插入區間”，在日常操作中，相信很多人在C++如何插入區間問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C++如何插入區間”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

插入區間

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

這道題讓我們在一系列非重疊的區間中插入一個新的區間，可能還需要和原有的區間合并，可以對給定的區間集進行一個一個的遍歷比較，那么會有兩種情況，重疊或是不重疊，不重疊的情況最好，直接將新區間插入到對應的位置即可，重疊的情況比較復雜，有時候會有多個重疊，需要更新新區間的范圍以便包含所有重疊，之后將新區間加入結果 res，最后將后面的區間再加入結果 res 即可。具體思路是，用一個變量 cur 來遍歷區間，如果當前 cur 區間的結束位置小于要插入的區間的起始位置的話，說明沒有重疊，則將 cur 區間加入結果 res 中，然后 cur 自增1。直到有 cur 越界或有重疊 while 循環退出，然后再用一個 while 循環處理所有重疊的區間，每次用取兩個區間起始位置的較小值，和結束位置的較大值來更新要插入的區間，然后 cur 自增1。直到 cur 越界或者沒有重疊時 while 循環退出。之后將更新好的新區間加入結果 res，然后將 cur 之后的區間再加入結果 res 中即可，參見代碼如下：

解法一：

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int n = intervals.size(), cur = 0;
        while (cur < n && intervals[cur][1] < newInterval[0]) {
            res.push_back(intervals[cur++]);
        }
        while (cur < n && intervals[cur][0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], intervals[cur][0]);
            newInterval[1] = max(newInterval[1], intervals[cur][1]);
            ++cur;
        }
        res.push_back(newInterval);
        while (cur < n) {
            res.push_back(intervals[cur++]);
        }
        return res;
    }
};

下面這種方法的思路跟上面的解法很像，只不過沒有用 while 循環，而是使用的是 for 循環，但是思路上沒有太大的區別，變量 cur 還是用來記錄新區間該插入的位置，稍有不同的地方在于在 for 循環中已經將新區間后面不重疊的區間也加進去了，for 循環結束后就只需要插入新區間即可，參見代碼如下：

解法二：

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int n = intervals.size(), cur = 0;
        for (int i = 0; i < n; ++i) {
            if (intervals[i][1] < newInterval[0]) {
                res.push_back(intervals[i]);
                ++cur;
            } else if (intervals[i][0] > newInterval[1]) {
                res.push_back(intervals[i]);
            } else {
                newInterval[0] = min(newInterval[0], intervals[i][0]);
                newInterval[1] = max(newInterval[1], intervals[i][1]);
            }
        }
        res.insert(res.begin() + cur, newInterval);
        return res;
    }
};

下面這種解法就是把上面解法的 for 循環改為了 while 循環，其他的都沒有變，代碼如下：

解法三：

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int n = intervals.size(), cur = 0, i = 0;
        while (i < n) {
            if (intervals[i][1] < newInterval[0]) {
                res.push_back(intervals[i]);
                ++cur;
            } else if (intervals[i][0] > newInterval[1]) {
                res.push_back(intervals[i]);
            } else {
                newInterval[0] = min(newInterval[0], intervals[i][0]);
                newInterval[1] = max(newInterval[1], intervals[i][1]);
            }
            ++i;
        }
        res.insert(res.begin() + cur, newInterval);
        return res;
    }
};

到此，關于“C++如何插入區間”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！