[leetcode] 88/ 21/23 Merge Sorte

合并数组

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

基本的 merge sort 思路, 双指针 + O(m+n) 的辅助空间 --> O(m+n) 的时间复杂度
注意处理一下 m 或 n 为 0 的情况

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> temp;
        temp = m ==0 ?nums2:nums1;
        int a=0,b=0;
        int i = 0;
        
            
        while(a<m && b<n){
            
            if(nums1[a] == nums2[b]){
                temp[i++] = nums1[a++];
                temp[i++] =  nums2[b++];
            }else if(nums1[a] > nums2[b]){
                temp[i++] =  nums2[b++];
            }else{
                temp[i++]= nums1[a++];
            }
            
            if(a == m){
                for(int k = b; k < n;k++){
                    temp[i++] =  nums2[b++];
                }
            }
            
            if(b==n){
                for(int k = a; k<m;k++){
                    temp[i++] = nums1[a++];
                }
            }    
        }
        
        for(int i = 0; i < nums1.size();i++){
            nums1[i] = temp[i];
        }

    }
};

image.png

合并链表

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

因为链表的删插是O(1)的，所以这里不需要额外O(K) 的空间。
直接操作指针完成merge.
由于我链表操作容易出错， 我这里采用递归的写法....（逃。

我这里的写法， 就是 保证 _mergeTwoLists（l1,l2）中l1的 val <= l2.val
这样 l1 就担当头指针的角色，每次递归只需要考虑是指向 l1.next 还是 l2
如果 l1.next 小, 则指向它， 继续递归_mergeTwoLists（l1.next.l2）
反之 递归_mergeTwoLists(l2 ，temp (l1.next) )
我们可以看到，递归始终保持 _mergeTwoLists（l1,l2）中l1的 val <= l2.val

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //处理空链表
        if(!l1) return l2;
        if(!l2) return l1;
        
        
        //保证 l1.val <= l2.val
        if(l1->val <= l2->val){
            _mergeTwoLists(l1,l2);
            return l1;
        }else{
            _mergeTwoLists(l2,l1);
            return l2;
        }
        
    }
private:
     void _mergeTwoLists(ListNode* l1, ListNode* l2) {
         
         if(!l1->next){
             l1->next = l2;
             return;
         }
         
         ListNode* temp ;
         //这样 l1 就变成头指针 选择指向 l1->next or l2
         if(l1->next->val <= l2->val){
             // 指向l1-next
             _mergeTwoLists(l1->next,l2);
         }else{
             //指向l2
             temp = l1->next;
             l1->next = l2;
             _mergeTwoLists(l2,temp);
         }
     }
    
};

image.png

merge K sorted lists

合并 K 个链表 和 合并上题目 合并 2 个 类似，
但是 需要额外开 O(k) 的空间， 借助 优先队列（最小堆） 来确定当前 头指针 到底指向谁。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <queue>
#include <vector>

using namespace std;

struct compare{
    bool operator()(const ListNode* a, const ListNode* b ){
        //greater
        return a->val > b->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode* >, compare> pq;
        
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        
        // 把K 个链表的头指针加入PQ
        for(auto& list:lists ){
            if(list){
                pq.push(list);
            }
        }
        // 链表全为空
        if(pq.empty()){
            return NULL;
        }
        // 每次 去除 最小值 
        // 让 当前指针 cur 指向 该最小值， 并把 cur 后移到最小值上
        // 如果 该最小值有 next ，加入 PQ
        while(!pq.empty()){
            cur->next = pq.top();
            pq.pop();
            cur = cur->next;
            if(cur->next)
                pq.push(cur->next);
        }
        return head->next;
        
    }
};

image.png