Day 16

第23题:

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。来源:力扣(LeetCode)

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

1、链表集合内的每个链表都是有序的,可以使用暴力求解,将K个链表的值依次放入到某个数组中;

  再利用快速排序将数组内值排序,再将数组值添加到链表返回即可,但是时间复杂度较高。

  也可以利用将集合内的K个链表分成K/2份,每份有两个链表,然后对两个链表内的值进行排序,返回两个链表的合并链表;

  最后会将所有的链表合并成一个链表并返回。

  

第378题:

给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。
请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。(来自LeetCode)

1、对于N*N的矩阵,内部每行每列都时升序排序,如果需要找第K小的值;

  可以将二位矩阵转换为一位数组,然后将一位数组排序得出升序数组,在其内部找出第K小的值。

  

2、官方题解里也用二分法可以将矩阵分成两部分,比较比中值mid小的个数和K的大小关系,

  比K大就说明第K小的值在左边这部分,如果比K大的话说明第K小的值在右边这部分;

  最终会得到第K小的值。

  

原文地址:https://www.cnblogs.com/liang-yi-/p/13228006.html