Merge questions
leetcode 88. Merge Sorted Array
题意
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.
代码（c++）
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m -1,j = n-1,k=m+n-1;
while(i>=0 && j >=0){
if(nums1[i] > nums2[j]){
nums1[k--] = nums1[i--];
}
else{
nums1[k--] = nums2[j--];
}
}
while(j >=0){
nums1[k--] = nums2[j--];
}
}
};
leetcode 21. Merge Two Sorted Lists
题意
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.
Subscribe to see which companies asked this question
代码（c++）
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode head = NULL;
ListNode *tmp = &head;
while (l1 && l2)
{
if (l1->val < l2->val)
{
tmp->next = l1;
l1 = l1->next;
}else{
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}
if (l1)
tmp->next = l1;
if(l2)
tmp->next = l2;
return head.next;
}
};
leetcode 23. Merge k Sorted Lists
题意
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
代码（c++）
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode head = NULL;
ListNode *tmp = &head;
while (l1 && l2)
{
if (l1->val < l2->val)
{
tmp->next = l1;
l1 = l1->next;
}else{
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}
if (l1)
tmp->next = l1;
if(l2)
tmp->next = l2;
return head.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size()==0)
return NULL;
ListNode *listNodeTmp = lists[0];
for(int i = 1;i<lists.size();i++){
listNodeTmp = mergeTwoLists(lists[i],listNodeTmp);
}
return listNodeTmp;
}
leetcode 56. Merge Intervals
题意
Given a collection of intervals, merge all overlapping intervals.
For example:
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
代码（c++）
class Solution {
public:
static int compare(Interval interval1, Interval interval2){
return interval1.start < interval2.start;
}
vector<Interval> merge(vector<Interval>& intervals) {
vector<Interval> res;
if (intervals.size()<=1) {
return intervals;
}
sort(intervals.begin(),intervals.end(), compare);
Interval interval = intervals[0] ;
for (int i=1; i<intervals.size(); i++) {
Interval tmp = intervals[i] ;
if (tmp.start > interval.end) {
res.push_back(interval);
interval = tmp;
continue;
}else{
interval.end = max(tmp.end, interval.end);
}
}
res.push_back(interval);
return res;
}
};
