[已解决]二维vector相关问题

DOLLAR.

在leetcode上刷题，最后自己在ide上试的时候发现写不来主函数....

/*以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi].
*请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。*/

/*
*author:Ambert
*date:2022/01/12
*/

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include<numeric>
#include <algorithm> 
using namespace std;

class Solution{
public:
        vector<vector<int>> merge(vector<vector<int>>& intervals){
                int n = intervals.size();
                if(n==0||n==1) return intervals;
                sort(intervals.begin(),intervals.end()); //使得数组内的数组有序 
                vector<vector<int>> merged;
                for(int i=0;i<n;++i){
                        int L=intervals[i][0],R=intervals[i][1]; //定义数组的最左指针和最右指针
                        if(!merged.size()||merged.back()[1]<L) //前一个的最右元素小于后一个数组最左元素则不变 
                                merged.push_back({L,R});
                        else
                                merged.back()[1]=max(merged.back()[1],R); //否则，取最大的一个更新最右元素 
                }
                return merged;
        }
};

int main(){
        vector<vector<int> > a = {{1,3},{2,6},{8,15},{10,18}};
        Solution solution;
        cout<<solution.merge(a)<<endl;
}

报错如下，请前辈指教

最佳答案

月排行榜 / 总排行榜

人造人

2022-1-14 11:58:19

/*以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi].
 *请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。*/

/*
 *author:Ambert
 *date:2022/01/12
 */

#include <algorithm>
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

class Solution {
public:
    //vector<vector<int>> merge(vector<vector<int>> &intervals) {
    const vector<vector<int>> merge(vector<vector<int>> &intervals) {
        int n = intervals.size();
        if(n == 0 || n == 1)
            return intervals;
        //sort(intervals.begin(), intervals.end()); //使得数组内的数组有序
        sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b) {return a[0] < b[0];}); //使得数组内的数组有序
        vector<vector<int>> merged;
        for(int i = 0; i < n; ++i) {
            int L = intervals[i][0],
                R = intervals[i][1]; //定义数组的最左指针和最右指针
            if(!merged.size() ||
                merged.back()[1] < L) //前一个的最右元素小于后一个数组最左元素则不变
                merged.push_back({L, R});
            else
                merged.back()[1] =
                    max(merged.back()[1], R); //否则，取最大的一个更新最右元素
        }
        return merged;
    }
};

ostream &operator<<(ostream &os, const vector<vector<int>> &rhs) {
    for(const auto &i: rhs) {
        for(const auto &j: i) {
            os << j << " ";
        }
        os << endl;
    }
    return os;
}

int main() {
    vector<vector<int>> a = {{1, 3}, {2, 6}, {8, 15}, {10, 18}};
    Solution solution;
    cout << solution.merge(a) << endl;
    return 0;
}

跳转到最佳答案楼层

Stubborn

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]

需要明确知道，我们在处理intervals ，会发生的情况，需要合并区间，或者合并不了区间，什么情况会发生，连续的任意两个区间【A, B】 和 【A`, B`】

第一覆盖的情况需要合并 【1， 6】【2， 3】：   A < A `   , B > B`
第二重叠的情况需要合并 【1， 6】【2， 8】：   A < A `   , B < B`
第三，不能合并【1， 6】【8， 10】：    A < A `   , B < B` ， 但是  A` > B  ，导致区间发生了‘隔离’

综合上面的情况，可以分成2类
1类，A` > B ，不能合并
2类，A` < B ,可以合并，从B , B` 选择大的一个数字

# intervals前提是排序好得，根据区间的起始位置。
result = []
result.append(intervals[0])
FOR E IN intervals:
    # 不能合并,把当前元素添加到结果集
    if E[0] > result[-1][1] :  result.append(E)
    #  能合并,从B or B` 选择大的元素跟新到列表
    else:  result[-1][1] = max( result[-1][1],  E[1])
    

人造人

/*以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi].
 *请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。*/

/*
 *author:Ambert
 *date:2022/01/12
 */

#include <algorithm>
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

class Solution {
public:
    //vector<vector<int>> merge(vector<vector<int>> &intervals) {
    const vector<vector<int>> merge(vector<vector<int>> &intervals) {
        int n = intervals.size();
        if(n == 0 || n == 1)
            return intervals;
        //sort(intervals.begin(), intervals.end()); //使得数组内的数组有序
        sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b) {return a[0] < b[0];}); //使得数组内的数组有序
        vector<vector<int>> merged;
        for(int i = 0; i < n; ++i) {
            int L = intervals[i][0],
                R = intervals[i][1]; //定义数组的最左指针和最右指针
            if(!merged.size() ||
                merged.back()[1] < L) //前一个的最右元素小于后一个数组最左元素则不变
                merged.push_back({L, R});
            else
                merged.back()[1] =
                    max(merged.back()[1], R); //否则，取最大的一个更新最右元素
        }
        return merged;
    }
};

ostream &operator<<(ostream &os, const vector<vector<int>> &rhs) {
    for(const auto &i: rhs) {
        for(const auto &j: i) {
            os << j << " ";
        }
        os << endl;
    }
    return os;
}

int main() {
    vector<vector<int>> a = {{1, 3}, {2, 6}, {8, 15}, {10, 18}};
    Solution solution;
    cout << solution.merge(a) << endl;
    return 0;
}

DOLLAR.

Stubborn 发表于 2022-1-13 11:46
需要明确知道，我们在处理intervals ，会发生的情况，需要合并区间，或者合并不了区间，什么情况会发生 ...

感谢，这两天没看帖子，我自己后来发现问题了：在主函数中不能直接cout数组

DOLLAR.

我把改好的代码贴出来，有需要的朋友可以看看

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm> 
using namespace std;

class Solution{
public:
        vector<vector<int>> mergeInterval(vector<vector<int>>& intervals){
                int n = intervals.size();
                if(n==0||n==1) return intervals;
                sort(intervals.begin(),intervals.end()); //是数组内的数组有序
                vector<vector<int>> merged;
                for(int i=0;i<n;++i){
                        int L=intervals[i][0],R=intervals[i][1]; //定义数组的最左指针位置及最右指针位置
                        if(!merged.size()||merged.back()[1]<L) //前一个的最右元素小于后一个数组的最左元素则不变
                                merged.push_back({L,R});
                        else
                                merged.back()[1]=max(merged.back()[1],R); //否则，取最大的一个元素更新最右指针
                }
                return merged;
        }
};

int main(){
        vector<vector<int>> a = {{1,3},{2,6},{8,15},{10,18}};
        Solution solution;
        vector<vector<int> > b = solution.mergeInterval(a);
        for (decltype(b.size()) i = 0; i < b.size(); ++i) {
            for (decltype(b[i].size()) j = 0; j < b[i].size(); ++j) {
                    cout << b[i][j] << " ";
                }
   //cout << endl;
        }
}

人造人

DOLLAR. 发表于 2022-1-17 13:07
我把改好的代码贴出来，有需要的朋友可以看看

我感觉还是重载operator<<
直接这样输出比较好 cout << solution.merge(a) << endl;

人造人

DOLLAR. 发表于 2022-1-17 13:07
我把改好的代码贴出来，有需要的朋友可以看看

这个 intervals 还是不要引用比较好，merge 这个函数不应该修改main函数中的那个变量a
虽然这样效率不高

    //vector<vector<int>> merge(vector<vector<int>> &intervals) {
    //const vector<vector<int>> merge(vector<vector<int>> &intervals) {
    const vector<vector<int>> merge(vector<vector<int>> intervals) {
        int n = intervals.size();
        if(n == 0 || n == 1)
            return intervals;
        //sort(intervals.begin(), intervals.end()); //使得数组内的数组有序
        sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b) {return a[0] < b[0];}); //使得数组内的数组有序
        vector<vector<int>> merged;
        for(int i = 0; i < n; ++i) {
            int L = intervals[i][0],
                R = intervals[i][1]; //定义数组的最左指针和最右指针
            if(!merged.size() ||
                merged.back()[1] < L) //前一个的最右元素小于后一个数组最左元素则不变
                merged.push_back({L, R});
            else
                merged.back()[1] =
                    max(merged.back()[1], R); //否则，取最大的一个更新最右元素
        }
        return merged;
    }