Algorithms: Sort
2 minute read
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].
融合数组的重复部分。1. 对数组进行排序。 2. 依次判断结果数组中最后一个间隔的重叠情况。
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节点插入到小于 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(n\log n)$，空间复杂度$O(1)$, 实现链表排序（归并、快排）
- 边界：链表为空或链表只有1个节点
- 思路：对一段列表划分成两段，分别对这两段进行排序，再对排好序的链表进行合并。 实际上，使用递归实现的归并排序空间复杂度为$O(\log n)$,递归工作栈大小应该为$O(\log n)$
归并方法
- merge函数，常用的两个排好序的链表融合，别忘了cur 往下走。
- 递归的结束条件：链表为空或链表长度为1，代表了最底层的返回值。
- 使用快慢指针对链表进行划分。
- 分别对两段调用递归排序，并合并。
- 时间复杂度：$O(n\log 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));
}
快排（此处给的是基于数组的，链表实现比较复杂）
- 思路：partition：对给定数组取基准元素，比它大的放它右边，比它小的放它左边。然后再将数组按返回的基准元素的位置进行划分，递归进行。
- 移动元素技巧性比较强
- 时间复杂度：$O(n\log n)$
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); //递归对高子表递归排序
}
}
