Divide and Conquer

23. Merge K Sorted Lists 合并k个有序链表

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Difficulty: Hard 合并k个排序列表.是前面21. Merge Two Sorted Lists 混合插入有序链表的升级版. 解法1 最先想到的就是利用21. Merge Two Sorted Lists 混合插入有序链表拿第一个链表与第二个合并,合并结果在于第三个比较.这样需要合并k-1次才能完成. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { int n = lists.

Median of Two Sorted Arrays两个数组的中位数

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Example1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example2 nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 分析 解法一: 思路来自Very concise O(log(min(M,N))) iterative solution with detailed explanation 看到O(log (m+n))一般来说就是分治法或是二分搜索,一个数组(长度为N)在中间切一刀,那它左边的索引L为(N-1)/2,右边的索引R为N/2.