merge sorted array

一、two array

1.两个有序链表合并(LC21)

1）题目
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
2）思路
循环两个链表，插入值更小的那一个，结束后如果指向某个链表的指针非空，用结果指针指向它。
3）代码

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* root = new ListNode(-1);auto res = root;while (l1 && l2) {if (l1->val <= l2->val) {res->next = l1;l1 = l1->next;}else {res->next = l2;l2 = l2->next;}res = res->next;}if (l1) res->next = l1;if(l2) res->next = l2;return root->next;
}

2.两个有序array原地合并(LC88)

1）题目
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
2）思路
直接合并入第一个array，从后往前合并，不会override array1.
3）代码

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int cur = m + n - 1;int i = m - 1, j = n - 1;while (i >= 0 && j >= 0) {while(i >= 0 && nums1[i] >= nums2[j]) nums1[cur--] = nums1[i--];while(i >= 0 && j >= 0 && nums2[j] >= nums1[i]) nums1[cur--] = nums2[j--];}while(j >= 0) nums1[cur--] = nums2[j--];
}

3.隐藏的有序array合并(LC977)

1）题目
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
2）思路
相当于从0或者正数和负数的分界点往两边合并array，但是从两头合并更节省时间，不需要寻找0的位置；相当于也是从大到小合并。
3）代码

vector<int> sortedSquares(vector<int>& nums) {int n = nums.size();vector<int> res(n);int cur = n - 1;int i = 0, j = cur;while (i <= j) {if (nums[i] * nums[i] >= nums[j] * nums[j]) {res[cur--] = nums[i] * nums[i];i++;}else {res[cur--] = nums[j] * nums[j];j--;}}return res;
}

二、合并k个array（LC23)

1.题目
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
2.思路
1）分治：两个两个合并，利用two array merge的方法
2）priority_queue：放入每个链表的头结点，依次取出值最小的进行链接
两种方法复杂度都是nlogk
3.做法
1)分治

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode* root = new ListNode(-1);auto res = root;while (l1 && l2) {if (l1->val <= l2->val) {res->next = l1;l1 = l1->next;}else {res->next = l2;l2 = l2->next;}res = res->next;}if (l1) res->next = l1;if(l2) res->next = l2;return root->next;
}ListNode* mergeKLists(vector<ListNode*>& lists) {int k = lists.size();if (!k) return NULL;while(k > 1) {int i = 0;for (i = 0; i + 1 < k; i += 2) {lists[i / 2] = mergeTwoLists(lists[i], lists[i + 1]);}if (i == k - 1) lists[k / 2] = lists[i];k = k / 2 + k % 2;}return lists[0];
}

2)priority_queue

struct cmp{bool operator ()(ListNode* a, ListNode* b) {return a->val > b->val;}
};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, cmp> q;ListNode* ans = new ListNode(-1);auto root = ans;for (auto t: lists) {if(t) q.push(t);}while(q.size()) {auto t = q.top();q.pop();root->next = t;root = root->next;if(t->next) {t = t->next;q.push(t);}}return ans->next;
}