链表-如快速将两个链表快速相加得到一个新的链表

题目

给出一个区间的集合，请合并所有重叠的区间。 示例：[[1,5],[2,7],[,10,18],[,17,19]] 结果：[[1,7],[10,19]] 为什么呢？[1,5] [2,7]有重叠3,4；[10,18],[17,19]有重叠17,18

我们分析上面的示例，其实比较的就是下一个区间起始值是否在上一个区间的范围内，依次比较，直到匹配失败，就把这个已经匹配过的最小值和最大值放入一个新的区间。
基于上面的思路，我们首先得保证区间是有序的（基于起始值的有序），所以先排序，这里我们学习一下快速排序算法。

快速排序

快速排序核心原理是经过一趟排序之后，使得这一组数据在某个值左边全是小于这个值的，在这个值的右边是大于这个值的，然后递归排序左边的数组和右边数组，直到最后数组的大小是0，排序终止，如下图，

• 第一次我们选取值为4的元素为中间值，经过一趟排序后，4的左边是2,3，右边是5
• 第二次我们对左边元素2,3,右边元素5进行排序，选取的中间值分别是2，5
• 第三次排序完成后,2,3有序，5有序
• 第四次每个数据只有只一个元素，终止排序

结合上面的题目我们用代码实现快速排序

func  QuickSort(intervals [][]int){
    //递归终止条件
    if len(intervals) <= 1 {
        return
    }
    head,tail = 0,len(intervals)-1
    //分区函数排序
    index := partion(intervals,head,tail)
    //递归左边的数组
    QuickSort(intervals[:index])
    //递归右边的数组
    QuickSort(intervals[index+1:])  
}

func partion(intervals [][]int,head,tail int) int{
    //选取一个中间值
    v := intervals[head][0]
    for head < tail{
       //比较末尾值和中间值，末尾值比中间值大，循环倒数第二个
        for head < tail && intervals[tail][0] >= v {
            tail--
        }
        //当末尾值大于中间值时，交换末尾值和中间值
        intervals[head],intervals[tail] = intervals[tail],intervals[head]
        //比较首部值和中间值，首部值比中间值小，继续下一个
        for head < tail && intervals[head][0] <= v{
            head++
        }
        //当首部值大于中间值时，交换中间值和首部值
        intervals[tail],intervals[head] = intervals[head],intervals[tail]
    }
    //返回中间值的下标
    return head
}

总结一下快速排序

快速排序是最常用的一种排序算法，在实际场景中也广泛用到，比如类库中（jdk类库），golang类库中，其排序算法都有用到快速排序。

• 快速排序使用了递归算法，每次分区之后，数组都会被切分成两个大小差不多相等的小区间，直到区间大小为1，这个过程需要log(n)次，每个区间进行排序需要遍历n（数组的结尾-开始）次，所以时间复杂度是nlog(n)，极端情况下会退化成n2,例如[1,2,3,4,5],这种情况下，数组是有序的，假设我们选的分区值是1，每次分区后两个数组的大小差距太大，最小为1，所以需要执行n次分区操作，那么时间复杂度会退化成n2。
• 他是一种原地排序算法，不会占用多余的空间，排序过程中除了申请一些临时变量存储，并无其它任何内存开销，所以空间复杂度是O(1),
• 他是一种不稳定的排序算法 ，因为在分区函数中回对数据元素做交换
• 快速排序的核心思想是分区和分治，分区时分区的值选取也很关键，一般采用中位数

快速排序的平均时间复杂度是nlog(n),其退化到n2的概率是非常小的，我们也可以选取合适的中间值进行避免，但他的原地排序，分治思想是非长优秀的，所以他在实际场景中应用广泛。

再回到一开始的问题

我们对intervals二位数组按下标为0的元素进行了升序排序，我们按照上面的解题思路开始实现代码

func merge(intervals [][]int) [][]int {
    //先判断，逻辑严谨性
    if len(intervals) == 0{
        retrun nil
    }
    //快速排序
    QuickSort(intervals)    
    //合并区间
    index := 0
    result := make([][]int,0)
    for index < len(intervals){
        //获取区间的左右值
        left := intervals[index][0]
        right := intervals[index][1]
         //判断下一个区间的起始值是否在上一个区间的范围
         //index下标小于二位数组长度-1，因为下一个区间是index+1，
         //已经排过序了，下一个区间的起始值只需要小于上一个区间的最大值
        for index < len(intervals)-1 && intervals[index+1][0] <= right {
           //获取区间的最大值
            index++
           right = max(right,intervals[index][1])
        }
        result = append(result,[]int{left,right})
        index++
    }
    return result
}

//最大值函数
fun max(a,b int) int{
    if a>b {
        return a
    }
    return b
}

欢迎大家关注微信公众号：“golang那点事”，更多精彩期待你的到来