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

DOLLAR.

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

1. /*以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi].
   
2. *请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。*/
   
3. 
   
4. /*
   
5. *author:Ambert
   
6. *date:2022/01/12
   
7. */
   
8. 
   
9. #include <stdio.h>
   
10. #include <stdlib.h>
    
11. #include <iostream>
    
12. #include <vector>
    
13. #include<numeric>
    
14. #include <algorithm>
    
15. using namespace std;
    
16. 
    
17. class Solution{
    
18. public:
    
19.         vector<vector<int>> merge(vector<vector<int>>& intervals){
    
20.                 int n = intervals.size();
    
21.                 if(n==0||n==1) return intervals;
    
22.                 sort(intervals.begin(),intervals.end()); //使得数组内的数组有序
    
23.                 vector<vector<int>> merged;
    
24.                 for(int i=0;i<n;++i){
    
25.                         int L=intervals[i][0],R=intervals[i][1]; //定义数组的最左指针和最右指针
    
26.                         if(!merged.size()||merged.back()[1]<L) //前一个的最右元素小于后一个数组最左元素则不变
    
27.                                 merged.push_back({L,R});
    
28.                         else
    
29.                                 merged.back()[1]=max(merged.back()[1],R); //否则，取最大的一个更新最右元素
    
30.                 }
    
31.                 return merged;
    
32.         }
    
33. };
    
34. 
    
35. int main(){
    
36.         vector<vector<int> > a = {{1,3},{2,6},{8,15},{10,18}};
    
37.         Solution solution;
    
38.         cout<<solution.merge(a)<<endl;
    
39. }

复制代码

报错如下，请前辈指教

最佳答案

月排行榜 / 总排行榜

人造人

2022-1-14 11:58:19

1. /*以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi].
   
2. *请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。*/
   
3. 
   
4. /*
   
5. *author:Ambert
   
6. *date:2022/01/12
   
7. */
   
8. 
   
9. #include <algorithm>
   
10. #include <iostream>
    
11. #include <numeric>
    
12. #include <stdio.h>
    
13. #include <stdlib.h>
    
14. #include <vector>
    
15. 
    
16. using namespace std;
    
17. 
    
18. class Solution {
    
19. public:
    
20.     //vector<vector<int>> merge(vector<vector<int>> &intervals) {
    
21.     const vector<vector<int>> merge(vector<vector<int>> &intervals) {
    
22.         int n = intervals.size();
    
23.         if(n == 0 || n == 1)
    
24.             return intervals;
    
25.         //sort(intervals.begin(), intervals.end()); //使得数组内的数组有序
    
26.         sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b) {return a[0] < b[0];}); //使得数组内的数组有序
    
27.         vector<vector<int>> merged;
    
28.         for(int i = 0; i < n; ++i) {
    
29.             int L = intervals[i][0],
    
30.                 R = intervals[i][1]; //定义数组的最左指针和最右指针
    
31.             if(!merged.size() ||
    
32.                 merged.back()[1] < L) //前一个的最右元素小于后一个数组最左元素则不变
    
33.                 merged.push_back({L, R});
    
34.             else
    
35.                 merged.back()[1] =
    
36.                     max(merged.back()[1], R); //否则，取最大的一个更新最右元素
    
37.         }
    
38.         return merged;
    
39.     }
    
40. };
    
41. 
    
42. ostream &operator<<(ostream &os, const vector<vector<int>> &rhs) {
    
43.     for(const auto &i: rhs) {
    
44.         for(const auto &j: i) {
    
45.             os << j << " ";
    
46.         }
    
47.         os << endl;
    
48.     }
    
49.     return os;
    
50. }
    
51. 
    
52. int main() {
    
53.     vector<vector<int>> a = {{1, 3}, {2, 6}, {8, 15}, {10, 18}};
    
54.     Solution solution;
    
55.     cout << solution.merge(a) << endl;
    
56.     return 0;
    
57. }
    

复制代码

跳转到最佳答案楼层

Stubborn

1. 
   
2. 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
   
3. 输出：[[1,6],[8,10],[15,18]]
   
4. 解释：区间 [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` 选择大的一个数字

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

复制代码

人造人

1. /*以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi].
   
2. *请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。*/
   
3. 
   
4. /*
   
5. *author:Ambert
   
6. *date:2022/01/12
   
7. */
   
8. 
   
9. #include <algorithm>
   
10. #include <iostream>
    
11. #include <numeric>
    
12. #include <stdio.h>
    
13. #include <stdlib.h>
    
14. #include <vector>
    
15. 
    
16. using namespace std;
    
17. 
    
18. class Solution {
    
19. public:
    
20.     //vector<vector<int>> merge(vector<vector<int>> &intervals) {
    
21.     const vector<vector<int>> merge(vector<vector<int>> &intervals) {
    
22.         int n = intervals.size();
    
23.         if(n == 0 || n == 1)
    
24.             return intervals;
    
25.         //sort(intervals.begin(), intervals.end()); //使得数组内的数组有序
    
26.         sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b) {return a[0] < b[0];}); //使得数组内的数组有序
    
27.         vector<vector<int>> merged;
    
28.         for(int i = 0; i < n; ++i) {
    
29.             int L = intervals[i][0],
    
30.                 R = intervals[i][1]; //定义数组的最左指针和最右指针
    
31.             if(!merged.size() ||
    
32.                 merged.back()[1] < L) //前一个的最右元素小于后一个数组最左元素则不变
    
33.                 merged.push_back({L, R});
    
34.             else
    
35.                 merged.back()[1] =
    
36.                     max(merged.back()[1], R); //否则，取最大的一个更新最右元素
    
37.         }
    
38.         return merged;
    
39.     }
    
40. };
    
41. 
    
42. ostream &operator<<(ostream &os, const vector<vector<int>> &rhs) {
    
43.     for(const auto &i: rhs) {
    
44.         for(const auto &j: i) {
    
45.             os << j << " ";
    
46.         }
    
47.         os << endl;
    
48.     }
    
49.     return os;
    
50. }
    
51. 
    
52. int main() {
    
53.     vector<vector<int>> a = {{1, 3}, {2, 6}, {8, 15}, {10, 18}};
    
54.     Solution solution;
    
55.     cout << solution.merge(a) << endl;
    
56.     return 0;
    
57. }
    

复制代码

DOLLAR.

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

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

DOLLAR.

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

1. #include <iostream>
   
2. #include <vector>
   
3. #include <numeric>
   
4. #include <algorithm>
   
5. using namespace std;
   
6. 
   
7. class Solution{
   
8. public:
   
9.         vector<vector<int>> mergeInterval(vector<vector<int>>& intervals){
   
10.                 int n = intervals.size();
    
11.                 if(n==0||n==1) return intervals;
    
12.                 sort(intervals.begin(),intervals.end()); //是数组内的数组有序
    
13.                 vector<vector<int>> merged;
    
14.                 for(int i=0;i<n;++i){
    
15.                         int L=intervals[i][0],R=intervals[i][1]; //定义数组的最左指针位置及最右指针位置
    
16.                         if(!merged.size()||merged.back()[1]<L) //前一个的最右元素小于后一个数组的最左元素则不变
    
17.                                 merged.push_back({L,R});
    
18.                         else
    
19.                                 merged.back()[1]=max(merged.back()[1],R); //否则，取最大的一个元素更新最右指针
    
20.                 }
    
21.                 return merged;
    
22.         }
    
23. };
    
24. 
    
25. int main(){
    
26.         vector<vector<int>> a = {{1,3},{2,6},{8,15},{10,18}};
    
27.         Solution solution;
    
28.         vector<vector<int> > b = solution.mergeInterval(a);
    
29.         for (decltype(b.size()) i = 0; i < b.size(); ++i) {
    
30.             for (decltype(b[i].size()) j = 0; j < b[i].size(); ++j) {
    
31.                     cout << b[i][j] << " ";
    
32.                 }
    
33.    //cout << endl;
    
34.         }
    
35. }

复制代码

人造人

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

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

人造人

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

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

1.     //vector<vector<int>> merge(vector<vector<int>> &intervals) {
   
2.     //const vector<vector<int>> merge(vector<vector<int>> &intervals) {
   
3.     const vector<vector<int>> merge(vector<vector<int>> intervals) {
   
4.         int n = intervals.size();
   
5.         if(n == 0 || n == 1)
   
6.             return intervals;
   
7.         //sort(intervals.begin(), intervals.end()); //使得数组内的数组有序
   
8.         sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b) {return a[0] < b[0];}); //使得数组内的数组有序
   
9.         vector<vector<int>> merged;
   
10.         for(int i = 0; i < n; ++i) {
    
11.             int L = intervals[i][0],
    
12.                 R = intervals[i][1]; //定义数组的最左指针和最右指针
    
13.             if(!merged.size() ||
    
14.                 merged.back()[1] < L) //前一个的最右元素小于后一个数组最左元素则不变
    
15.                 merged.push_back({L, R});
    
16.             else
    
17.                 merged.back()[1] =
    
18.                     max(merged.back()[1], R); //否则，取最大的一个更新最右元素
    
19.         }
    
20.         return merged;
    
21.     }
    

复制代码