给出一个区间的集合,请合并所有重叠的区间。 示例:[[1,5],[2,7],[,10,18],[,17,19]] 结果:[[1,7],[10,19]] 为什么呢?[1,5] [2,7]有重叠3,4;[10,18],[17,19]有重叠17,18
我们分析上面的示例,其实比较的就是下一个区间起始值是否在上一个区间的范围内,依次比较,直到匹配失败,就把这个已经匹配过的最小值和最大值放入一个新的区间。
基于上面的思路,我们首先得保证区间是有序的(基于起始值的有序),所以先排序,这里我们学习一下快速排序算法。
快速排序核心原理是经过一趟排序之后,使得这一组数据在某个值左边全是小于这个值的,在这个值的右边全是大于这个值的,然后递归排序左边的数组和右边数组,直到最后数组的大小是1,排序终止,如下图,
结合上面的题目我们用代码实现快速排序
快速排序是最常用的一种排序算法,在实际场景中也广泛用到,比如类库中(jdk类库,golang类库)其排序算法都有用到快速排序。
快速排序的平均时间复杂度是nlog(n),其退化到n2的概率是非常小的,我们也可以选取合适的中间值进行避免,但他的原地排序,分治思想是非常优秀的,所以他在实际场景中应用广泛。
我们对intervals二位数组按下标为0的元素进行了升序排序,我们按照上面的解题思路开始实现代码