LeetCode 剑指 Offer II 排序 专题总结

unordered_map<int, int> map;

for(int i = 0; i < arr2.size(); i++)

map[arr2[i]] = i;

sort(arr1.begin(), arr1.end(), [&](int x, int y) {

if(map.count(x)) {

return map.count(y)? map[x] < map[y] : true;

}else {

return map.count(y)? false : x < y;

}

});

return arr1;

}

};

[](()076. 数组中的第 k 大的数字

=================================================================================

题目：

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例：

输入: [3,2,1,5,6,4] 和 k = 2

输出: 5

提示：

• 1 <= k <= nums.length <= 104

• -104 <= nums[i] <= 104

思路：

优先队列（大根堆）

第K大 等价于 第n = nums.size() - k + 1 小，所以我们存储最小的 n 个元素，堆顶就是第 k 大元素

当堆达到 n + 1时 将堆顶移除，这样就可以保持将 大于 第k大的元素移除掉

class Solution {

public:

int findKthLargest(vector<int>& nums, int k) {

// 第 k 大就是第 nums.size() - k + 1 小；

// 小到大排序

priority_queue<int, vector<int>, less<int>> pq;

int n = nums.size() - k + 1;

for(int i : nums) {

pq.emplace(i);

if(pq.size() > n) pq.pop();

}

return pq.top();

}

};

[](()077. 链表排序

=========================================================================

题目：

给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例：

输入：head = [4,2,1,3]

输出：[1,2,3,4]

提示：

• 链表中节点的数目在范围 [0, 5 * 104] 内

• -105 <= Node.val <= 105

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

思路：

归并思想：找中点 + 递归成单个链表节点 + 合并链表

找中点时记得将中点的前一个与后面断开

class Solution {

public:

// 找中点 + 递归成单个链表节点 + 合并链表

ListNode* sortList(ListNode* head) {

// 到只剩一个元素返回

if(head == nullptr || head->next == nullptr)

return head;

// 数组分成两段并返回中点

ListNode* head1 = head;

ListNode* head2 = serachMid(head);

head1 = sortList(head1);

head2 = sortList(head2);

// 合并并返回

return merge(head1,head2);

}

// 找中点

ListNode* serachMid(ListNode* head) {

ListNode *slow = head, *fast = head;

while(fast->next && fast->next->next) {

slow = slow->next;

fast = fast->next->next;

}

ListNode* mid = slow->next;

slow->next = nullptr;

return mid;

}

// 合并链表

ListNode* merge(ListNode* head1, ListNode* head2) {

ListNode* dummy = new ListNode(-1);

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;

}

if(head1) cur->next = head1;

if(head2) cur->next = head2;

return dummy->next;

}

};

[](()078. 合并排序链表（困难）

===== 《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 ==========================================================================

题目：

给定一个链表数组，每个链表都已经按升序排列。

请将所有链表合并到一个升序链表中，返回合并后的链表。

示例：

输入：lists = [[1,4,5],[1,3,4],[2,6]]

输出：[1,1,2,3,4,4,5,6]

解释：链表数组如下：

[

1->4->5,

1->3->4,

2->6

]

将它们合并到一个有序链表中得到。

1->1->2->3->4->4->5->6

提示：

• k == lists.length

• 0 <= k <= 10^4

• 0 <= lists[i].length <= 500

• -10^4 <= lists[i][j] <= 10^4

• lists[i] 按 升序 排列

• lists[i].length 的总和不超过 10^4

思路：

优先队列（小根堆）的两个思路：

首先我用的方法一，然后一直报堆栈溢出错误，后来用的方法二，然后发现方法一是可能会发生循环

解决：在加入堆后，将本节点的next节点去掉

• 方法一：先将所有节点入队列（需重写优先队列的排序方法），然后遍历队列将所有节点连接起来

也可以将节点值直接加入队列（不需要重写排序方法），但是连接节点时需要重新创建节点

• 方法二：将每个链表头加入堆，然后重新连接节点后将次节点的下一个节点重新入堆，思想跟 [LeetCode 剑指 Offer II 061. 和最小的 k 个数对](()很像，可以参考我的题解 [LeetCode 剑指 Offer II 堆 专题总结](()

方法一、小根堆 + 全部入堆

class Solution {

public:

// 小根堆 + 全部入堆

ListNode* mergeKLists(vector<ListNode*>& lists) {

auto cmp = [&](ListNode* node1, ListNode* node2){

return node1->val > node2->val;

};

priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

ListNode* dummy = new ListNode(-1);

ListNode* ans = dummy;

for(auto& head : lists) {

ListNode* cur = head;

while(cur) {

pq.emplace(cur);

// 加入后将后节点去掉 不然可能循环

ListNode* pre = cur;

cur = cur->next;

pre->next = nullptr;

}

}

while(!pq.empty()) {

ListNode* node = pq.top();

pq.pop();

cout << node->val << endl;

ans->next = node;

ans = ans->next;

}

return dummy->next;

}

};

方法二、小根堆 + 加入子链表头结点

class Solution {

public:

// 小根堆 + 子链表头结点先入堆

ListNode* mergeKLists(vector<ListNode*>& lists) {

auto cmp = [&](ListNode* node1, ListNode* node2){

return node1->val > node2->val;

};

priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);