对网站建设在电子商务中的看法,做网站哪个便宜,公司网站怎么建立优化体系,做网站的教科书目录
归并排序详解
递归实现
迭代实现
面试题 77 : 链表排序
面试题 78 : 合并排序链表
法一、利用最小堆选取值最小的节点
法二、按照归并排序的思路合并链表 归并排序详解
归并排序就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表…目录
归并排序详解
递归实现
迭代实现
面试题 77 : 链表排序
面试题 78 : 合并排序链表
法一、利用最小堆选取值最小的节点
法二、按照归并排序的思路合并链表 归并排序详解
归并排序就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为 2-路归并。
归并排序算法的思想是假设初始列表含有 n 个记录则可看成 n 个有序的子序列每个子序列的长度为 1然后两两归并得到 个长度为 2 或 1 的有序子序列再两两归并··· ···如此重复直至得到一个长度为 n 的有序序列为止。 递归实现 class Solution {
public:vectorint sortArray(vectorint nums) {int n nums.size();vectorint tmp(n);mergeSort(nums, tmp, 0, n - 1);return nums;}
private:void mergeSort(vectorint nums, vectorint tmp, int left, int right) {if (left right)return;int mid (left right) / 2;mergeSort(nums, tmp, left, mid);mergeSort(nums, tmp, mid 1, right);
// 合并相邻的两个有序子序列 nums[left···mid] 和 nums[mid1···right]int i left, j mid 1, k left;while (i mid j right){if (nums[i] nums[j])tmp[k] nums[i];elsetmp[k] nums[j];}while (i mid){tmp[k] nums[i];}while (j right){tmp[k] nums[j];}
for (int i left; i right; i){nums[i] tmp[i];}}
}; 迭代实现
class Solution {
public:vectorint sortArray(vectorint nums) {int n nums.size();vectorint tmp(n);for (int seg 1; seg n; seg * 2){for (int left 0; left n; left 2 * seg){int mid min(left seg - 1, n - 1);int right min(left 2 * seg - 1, n - 1);int i left, j mid 1, k left;while (i mid j right){if (nums[i] nums[j])tmp[k] nums[i];elsetmp[k] nums[j];}while (i mid){tmp[k] nums[i];}while (j right){tmp[k] nums[j];}}nums tmp;}return nums;}
};
由于长度为 n 的数组每次都被分为两个长度为 n/2 的数组因此不管输入什么样的数组归并排序的时间复杂度都是 O(nlog)。归并排序需要创建一个长度为 n 的辅助空间。如果用递归实现归并排序那么递归的调用栈需要 O(logn) 的空间。因此归并排序的空间复杂度是 O(n)。
手写归并排序的代码本身就是很常见的面试题因此应聘者应深刻理解归并排序的过程熟悉归并排序的迭代和归并的代码实现。同时归并排序是应用分治法来解决问题的类似的思路可以用来解决很多其他的问题。 面试题 77 : 链表排序
题目
输入一个链表的头节点请将该链表排序。例如输入下图 (a) 中的链表该链表排序后如下图 (b) 所示。 分析
可以使用归并排序对链表进行排序其主要思想是将链表分成两个子链表在对两个子链表排序之后再将它们合并成一个排序的链表。排序子链表和排序整个链表是同一个问题可以递归调用同一个函数解决。
class Solution {
public:ListNode* sortList(ListNode* head) {if (head nullptr || head-next nullptr)return head;ListNode* head1 head;ListNode* head2 split(head);
head1 sortList(head1);head2 sortList(head2);
return merge(head1, head2);}
private:ListNode* split(ListNode* head) {ListNode* slow head;ListNode* fast head-next;while (fast fast-next){slow slow-next;fast fast-next-next;}ListNode* secondHead slow-next;slow-next nullptr;return secondHead;}
ListNode* merge(ListNode* head1, ListNode* head2) {ListNode* dummy new ListNode;ListNode* cur dummy;while (head1 head2){if (head1-val head2-val){cur-next head1;head1 head1-next;}else{cur-next head2;head2 head2-next;}cur cur-next;}cur-next head1 ! nullptr ? head1 : head2;return dummy-next;}
}; 函数 split 将链表分成前后两半并返回后半部分链表的头节点。 可以用快慢指针的思路将链表分成前后两半其中慢指针一次走一步快指针一次走两步。 如果链表的节点总数为偶数那么当快指针走到链表的尾节点时慢指针正好走到前半段链表的最后一个节点前半段链表和后半段链表的节点个数相同。 如果链表的节点总数为奇数那么当快指针走到空时慢指针也正好走到前半段链表的最后一个节点前半段链表比后半段链表多一个节点。 函数 merge 用来合并两个排序的子链表并返回合并后的排序链表的头节点。 和合并两个排序的子数组类似也可以用两个指针分别指向两个排序子链表的节点然后选择其中值较小的节点。与合并数组不同的是不需要另一个链表来保存合并之后的节点而只需要调整指针的指向。 面试题 78 : 合并排序链表
题目
输入 k 个排序的链表请将它们合并成一个排序的链表。例如输入 3 个排序的链表如下图 (a) 所示将它们合并之后得到的排序的链表如下图 (b) 所示。 法一、利用最小堆选取值最小的节点
用 k 个指针分别指向这 k 个链表的头节点从这 k 个节点中选取值最小的节点。然后将指向值最小的节点的指针向后移动一步再比较 k 个指针指向的节点并选取值最小的节点。重复这个过程直到所有节点都被选取出来。
这思路需要反复比较 k 个节点并选取值最小的节点。既可以每次都用一个 for 循环用 O(k) 的时间复杂度比较 k 个节点的值也可以将 k 个节点放入一个最小堆中位于堆顶的节点就是值最小的节点。每当选取某个值最小的节点之后将它从堆中删除并将它的下一个节点添加到堆中。从最小堆中得到位于堆顶的节点的时间复杂度是 O(1)堆的删除和插入操作的时间复杂度是 O(logk)因此使用最小堆比直观地用 for 循环的时间效率高。
struct Greater {bool operator()(const ListNode* lhs, const ListNode* rhs){return lhs-val rhs-val;}
};
class Solution {
public:ListNode* mergeKLists(vectorListNode* lists) {ListNode* dummy new ListNode;ListNode* cur dummy;
priority_queueListNode*, vectorListNode*, Greater minHeap;for (ListNode* head : lists){if (head)minHeap.push(head);}
while (!minHeap.empty()){cur-next minHeap.top();minHeap.pop();cur cur-next;if (cur-next)minHeap.push(cur-next);}return dummy-next;}
}; 假设 k 个排序链表总共有 n 个节点。如果堆的大小为 k那么空间复杂度就是 O(k)。每次用最小堆处理一个节点需要 O(logk) 的时间因此这种解法的时间复杂度是 O(nlogk)。 法二、按照归并排序的思路合并链表
下面换一种思路来解决这个问题。输入的 k 个排序链表可以分成两部分前 k/2 个链表和后 k/2 个链表。如果将前 k/2 个链表和后 k/2 个链表分别合并成两个排序的链表再将这两个排序的链表合并那么所有链表都合并了。合并 k/2 个链表与合并 k 个链表是同一个问题可以调用递归函数解决。
class Solution {
public:ListNode* mergeKLists(vectorListNode* lists) {if (lists.size() 0)return nullptr;return mergeTwoList(lists, 0, lists.size() - 1);}
private:ListNode* mergeTwoList(vectorListNode* lists, int left, int right) {if (left right)return lists[left];int mid (left right) / 2;ListNode* head1 mergeTwoList(lists, left, mid);ListNode* head2 mergeTwoList(lists, mid 1, right);
ListNode* dummy new ListNode;ListNode* cur dummy;while (head1 head2){if (head1-val head2-val){cur-next head1;head1 head1-next;}else{cur-next head2;head2 head2-next;}cur cur-next;}cur-next head1 ! nullptr ? head1 : head2;return dummy-next;}
};
