合并数组
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];
}
}
};
合并链表
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);
}
}
};
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;
}
};
