快捷導(dǎo)航

C++實(shí)現(xiàn)LeetCode(56.合并區(qū)間)

更新時(shí)間：2021年07月16日 09:09:21 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(56.合并區(qū)間),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 56. Merge Intervals 合并區(qū)間

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

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

這道和之前那道 Insert Interval 很類似，這次題目要求我們合并區(qū)間，之前那題明確了輸入?yún)^(qū)間集是有序的，而這題沒有，所以我們首先要做的就是給區(qū)間集排序，由于我們要排序的是個(gè)結(jié)構(gòu)體，所以我們要定義自己的 comparator，才能用 sort 來排序，我們以 start 的值從小到大來排序，排完序我們就可以開始合并了，首先把第一個(gè)區(qū)間存入結(jié)果中，然后從第二個(gè)開始遍歷區(qū)間集，如果結(jié)果中最后一個(gè)區(qū)間和遍歷的當(dāng)前區(qū)間無重疊，直接將當(dāng)前區(qū)間存入結(jié)果中，如果有重疊，將結(jié)果中最后一個(gè)區(qū)間的 end 值更新為結(jié)果中最后一個(gè)區(qū)間的 end 和當(dāng)前 end 值之中的較大值，然后繼續(xù)遍歷區(qū)間集，以此類推可以得到最終結(jié)果，代碼如下：

解法一:

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> res{intervals[0]};
        for (int i = 1; i < intervals.size(); ++i) {
            if (res.back()[1] < intervals[i][0]) {
                res.push_back(intervals[i]);
            } else {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            }
        }   
        return res;
    }
};

下面這種解法將起始位置和結(jié)束位置分別存到了兩個(gè)不同的數(shù)組 starts 和 ends 中，然后分別進(jìn)行排序，之后用兩個(gè)指針i和j，初始化時(shí)分別指向 starts 和 ends 數(shù)組的首位置，然后如果i指向 starts 數(shù)組中的最后一個(gè)位置，或者當(dāng) starts 數(shù)組上 i+1 位置上的數(shù)字大于 ends 數(shù)組的i位置上的數(shù)時(shí)，此時(shí)說明區(qū)間已經(jīng)不連續(xù)了，我們來看題目中的例子，排序后的 starts 和 ends 為：

starts: 1 2 8 15

ends: 3 6 10 18

紅色為i的位置，藍(lán)色為j的位置，那么此時(shí) starts[i+1] 為8，ends[i] 為6，8大于6，所以此時(shí)不連續(xù)了，將區(qū)間 [starts[j], ends[i]]，即 [1, 6] 加入結(jié)果 res 中，然后j賦值為 i+1 繼續(xù)循環(huán)，參見代碼如下：

解法二：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<vector<int>> res;
        vector<int> starts, ends;
        for (int i = 0; i < n; ++i) {
            starts.push_back(intervals[i][0]);
            ends.push_back(intervals[i][1]);
        }
        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());
        for (int i = 0, j = 0; i < n; ++i) {
            if (i == n - 1 || starts[i + 1] > ends[i]) {
                res.push_back({starts[j], ends[i]});
                j = i + 1;
            }
        } 
        return res;
    }
};

這道題還有另一種解法，這個(gè)解法直接調(diào)用了之前那道題 Insert Interval 的函數(shù)，由于插入的過程中也有合并的操作，所以我們可以建立一個(gè)空的集合，然后把區(qū)間集的每一個(gè)區(qū)間當(dāng)做一個(gè)新的區(qū)間插入結(jié)果中，也可以得到合并后的結(jié)果，那道題中的四種解法都可以在這里使用，但是沒必要都列出來，這里只選了那道題中的解法二放到這里，代碼如下：

解法三：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        for (int i = 0; i < intervals.size(); ++i) {
            res = insert(res, intervals[i]);
        }
        return res;
    }
    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;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(56.合并區(qū)間)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)合并區(qū)間內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: