文章目录
- 一、题目
- 二、解法
- 三、完整代码
所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
一、题目
二、解法
思路分析:本题比较简单。排序+判断交集即可实现。博主给出两版代码,第一版运行时间稍长,占用内存小,因为快排函数和erase函数都比较占用时间。
程序如下:
// 第一版
class Solution {static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];return a[0] < b[0];}
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);for (int i = 0; i < intervals.size() - 1; i++) {if (intervals[i][1] >= intervals[i + 1][0]) { // 如果第i个区间和第i-1个区间挨着intervals[i][1] = max(intervals[i][1], intervals[i + 1][1]); // 合并区间intervals.erase(intervals.begin() + i + 1);i--;}}return intervals;}
};
运行时间较短,但是多用了一个result变量,占用内存较大,比较函数cmp用lambda表达式代替了。
// 第二版
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end(), [](const vector<int>&a, const vector<int> b){ return a[0] < b[0]; }); // 排序函数用了lambda表达式vector<vector<int>> result;result.push_back(intervals[0]);for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) { // 如果第i个区间和第i-1个区间挨着result.back()[1] = max(result.back()[1], intervals[i][1]); // 合并区间}else result.push_back(intervals[i]);}return result;}
};
复杂度分析:
- 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn),一个快速排序。
- 空间复杂度: O ( 1 ) O(1) O(1),有一个快排,最差情况(倒序)时,需要n次递归调用。因此确实需要O(n)的栈空间
可以看出代码并不复杂。
三、完整代码
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;//class Solution {
//public:
// vector<vector<int>> merge(vector<vector<int>>& intervals) {
// sort(intervals.begin(), intervals.end(), [](const vector<int>&a, const vector<int> b){ return a[0] < b[0]; }); // 排序函数用了lambda表达式
// vector<vector<int>> result;
// result.push_back(intervals[0]);
// for (int i = 1; i < intervals.size(); i++) {
// if (result.back()[1] >= intervals[i][0]) { // 如果第i个区间和第i-1个区间挨着
// result.back()[1] = max(result.back()[1], intervals[i][1]); // 合并区间
// }
// else result.push_back(intervals[i]);
// }
// return result;
// }
//};class Solution {static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];return a[0] < b[0];}
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);for (int i = 0; i < intervals.size() - 1; i++) {if (intervals[i][1] >= intervals[i + 1][0]) { // 如果第i个区间和第i-1个区间挨着intervals[i][1] = max(intervals[i][1], intervals[i + 1][1]); // 合并区间intervals.erase(intervals.begin() + i + 1);i--;}}return intervals;}
};int main() {//vector<vector<int>> intervals = { {1, 3}, {2, 6},{8, 10},{15, 18} };vector<vector<int>> intervals = { {1, 4}, {0, 2},{3, 5} };Solution s1;vector<vector<int>> result = s1.merge(intervals);for (vector<vector<int>>::iterator it = result.begin(); it != result.end(); it++) {for (vector<int>::iterator jt = (*it).begin(); jt != (*it).end(); jt++) {cout << *jt << " ";}cout << endl;} system("pause");return 0;
}
end