leetcode56合并区间

雨点打透心脏的1/2处 2022-09-09 04:59 216阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_16_color_FFFFFF_t_70_g_se_x_16]  
思路

1.  转成结构体
2.  对结构体进行排序，以start为排序参数
3.  注意比较结尾处两个的大小

#include<stdio.h>
    #include<stdlib.h>
     struct Inter{ 
        int start;
        int end;
    };
    int cmp(const void *a,const void *b){ 
        struct Inter c = *(struct Inter*) a;
        struct Inter d = *(struct Inter*) b;
        return  c.start - d.start;
    }
    
    #define max(a,b) ((a)>(b)?a:b)
    int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){ 
        struct Inter inter[intervalsSize];
        int i,j;
        for(i=0;i<intervalsSize;i++){ 
            inter[i].start=intervals[i][0];
            inter[i].end=intervals[i][1];
        }
        qsort(inter, intervalsSize, sizeof(struct Inter),cmp);
        struct Inter res[intervalsSize];
        i=1;j=1;
        res[0].start = inter[0].start;
        res[0].end = inter[0].end;
        while (i<intervalsSize)
        { 
            if(inter[i].start<=res[j-1].end){ 
                res[j-1].end=max(inter[i].end,res[j-1].end);//注意这 取最大的
                i++;
            }
            else { 
                res[j].start = inter[i].start;
                res[j].end = inter[i].end;
                i++;j++;
            }
        }
    
        int **ress = (int**)malloc(sizeof(int*)*j);
        for(i=0;i<j;i++){ 
            ress[i] = (int*)malloc(sizeof(int)*2);
        }
        for(i=0;i<j;i++){ 
            //printf("start = %d end = %d\n",res[i].start,res[i].end);
            ress[i][0] = res[i].start;
            ress[i][1] = res[i].end;
        }
        * returnSize = j;
        int len = 2;
        * returnColumnSizes =intervalsColSize ;//这个地方 直接用上面的参数
        return ress;
    }
    
    int main(){ 
        int inter[5][2] ={ { 1,3},{ 2,6},{ 8,10},{ 15,18}};
        int intervalsSize = 4;
        int intervalsColSize = 2;
        int returnSize = 0;
        int len = 2;
        int * returnColumnSizes = &len;
        int **res = merge((int**)inter,intervalsSize,&intervalsColSize,&returnSize,&returnColumnSizes);
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/e7a9e64d93c34156afa122c25761e586.png