当前位置：首页 > news >正文

leetcode56--合并数组

news 来源：原创 2024/5/14 11:50:12

1. 题意

将给定区间合并为不相交的若干个区间。
合并数组

2. 题解

先进行排序，再根据是否相交进行合并。

2.1 我的代码

class Solution {
public:struct int_cmp {static bool cmp(const vector<int> &a, const vector<int> &b) {if (a[0] != b[0])return a[0] < b[0];return a[1] < b[1];}};bool isOverlap(const vector<int> &a,const vector<int> &b) {if (a.empty() || b.empty())return true;return a[1] >= b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), int_cmp::cmp);vector<vector<int>> ans;vector<int> cur;int cnt = 0;for (auto &interval: intervals) {   //std::cout << interval[0] << ":" << interval[1] << std::endl;if ( isOverlap(cur, interval) ) {if (cur.empty())cur = interval;else  {cur[1] = max(cur[1], interval[1]);}}else {ans.emplace_back(cur);cur = interval;}}ans.emplace_back(cur);return ans;}
};

2.2 桶排序

跟括号匹配一样的思路

class Solution {public:vector<vector<int>> merge(vector<vector<int>>& intervals) {int n = intervals.size();int left = 10000, right = 0;for (vector<int>& interval : intervals) {left = min(left, interval[0]);right = max(right, interval[1]);}vector<int> buckets(right-left+1, 0);vector<bool> existed(right-left+1, false);for (vector<int>& interval : intervals) {buckets[interval[0]-left]++;buckets[interval[1]-left]--;existed[interval[0]-left] = true;existed[interval[1]-left] = true;}int cnt = 0, last = -1;vector<vector<int>> res;for (int i = left; i <= right; i++) {cnt += buckets[i-left];if (cnt == 0) {if (last != -1) {res.push_back({last, i});last = -1;} else if (existed[i-left]) {res.push_back({i, i});}} else if (last == -1) {last = i;}}return res;}
};作者：明天更要加油啊
链接：https://leetcode.cn/problems/merge-intervals/solutions/2678187/bi-guan-fang-ti-jie-geng-you-xiu-de-onji-zw2x/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。