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].
融合數(shù)組的重復部分囊卜。1. 對數(shù)組進行排序练俐。 2. 依次判斷結果數(shù)組中最后一個間隔的重疊情況璃俗。
vector<Interval> merge(vector<Interval>& intervals) {
std::sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){return a.start < b.start;});
vector<Interval> res;
if (intervals.empty()) return res;
res.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); ++i) {
Interval cur = intervals[i];
Interval last = res.back();
if (cur.start <= last.end) {
res[res.size() - 1].end = max(cur.end, last.end);
} else {
res.push_back(cur);
}
}
return res;
}
對鏈表使用插入排序涌乳。使用指針preHead指向拍好序的鏈表迎瞧，head指向未排序的鏈表，指針pt是拍好序的鏈表的游標逗抑，當head->val 小于等于 pt->next->val時剧辐，pt向前移動。pt在 pt -> next == NULL時邮府，插在末尾；在另一種結束情況溉奕，代表head節(jié)點插入到小于 pt -> next -> val的pt和pt->next之間褂傀。
時間復雜度：O(n^2)
ListNode* insertionSortList(ListNode* head) {
ListNode preHead = ListNode(INT_MIN);
while (head) {
ListNode *pt = &preHead;
while (pt -> next && pt -> next ->val <= head->val) {
pt = pt -> next;
}
ListNode *next = head -> next;
head -> next = pt -> next;
pt -> next = head;
head = next;
}
return preHead.next;
}
解析: 時間復雜度O(nlogn)，空間復雜度O(1), 實現(xiàn)鏈表排序（歸并加勤、快排）
邊界：鏈表為空或鏈表只有1個節(jié)點
思路：對一段列表劃分成兩段仙辟，分別對這兩段進行排序，再對排好序的鏈表進行合并鳄梅。 實際上叠国，使用遞歸實現(xiàn)的歸并排序空間復雜度為O(logn),遞歸工作棧大小應該為O(logn)
1. merge函數(shù)，常用的兩個排好序的鏈表融合戴尸，別忘了cur 往下走粟焊。
2. 遞歸的結束條件：鏈表為空或鏈表長度為1，代表了最底層的返回值孙蒙。
3. 使用快慢指針對鏈表進行劃分项棠。
4. 分別對兩段調用遞歸排序，并合并挎峦。
時間復雜度：O(nlogn)
// 歸并香追，使用分治思想，這個實現(xiàn)一定要熟悉
ListNode* mergeLists(ListNode *left, ListNode *right) {
ListNode preHead = ListNode(INT_MIN);
ListNode *cur = &preHead;
while (left && right) {
if (left->val < right->val) {
cur -> next = left;
left = left -> next;
} else {
cur -> next = right;
right = right -> next;
}
cur = cur -> next;
}
cur -> next = left?left:right;
return preHead.next;
}
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode preHead = ListNode(INT_MIN);
preHead.next = head;
ListNode *preMid = &preHead, *mid = head;
while (head && head -> next) {
preMid = mid;
mid = mid -> next;
head = head -> next -> next;
}
preMid -> next = NULL;
return mergeLists(sortList(preHead.next),sortList(mid));
}
快排（此處給的是基于數(shù)組的坦胶，鏈表實現(xiàn)比較復雜）
思路：partition：對給定數(shù)組取基準元素透典，比它大的放它右邊，比它小的放它左邊顿苇。然后再將數(shù)組按返回的基準元素的位置進行劃分峭咒，遞歸進行。
1. 移動元素技巧性比較強
時間復雜度：O(nlogn)
int partition(int a[], int low, int high)
{
int privotKey = a[low]; //基準元素
while(low < high){ //從表的兩端交替地向中間掃描
while(low < high && a[high] >= privotKey) --high; //從high 所指位置向前搜索岖圈，至多到low+1 位置讹语。將比基準元素小的交換到低端
swap(&a[low], &a[high]);
while(low < high && a[low] <= privotKey ) ++low;
swap(&a[low], &a[high]);
}
print(a,10);
return low;
}
void quickSort(int a[], int low, int high){
if(low < high){
int privotLoc = partition(a, low, high); //將表一分為二
quickSort(a, low, privotLoc -1); //遞歸對低子表遞歸排序
quickSort(a, privotLoc + 1, high); //遞歸對高子表遞歸排序
}
}
