25寒假算法刷题 | LeetCode 240. 搜索二维矩阵 II，148. 排序链表

目录

• 240. 搜索二维矩阵 II
• • 题目描述
  • 题解
• 148. 排序链表
• • 题目描述
  • 题解

240. 搜索二维矩阵 II

点此跳转题目链接

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matrix[i][j] <= 109
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -109 <= target <= 109

题解

暴力算法直接遍历整个矩阵，时间复杂度为 $O(mn)$ ， $m、n$ 分别为矩阵的行、列数。

由于题中矩阵在行和列上的元素都是升序的，所以想到可以从上到下逐行利用二分查找解决：

class Solution {public: int binarySearch(const vector<int>& arr, int target) { int left = 0; int right = arr.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] < target) { left = mid + 1; } else if (arr[mid] > target) { right = mid - 1; } else { return mid; } } return -1; } bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty()) { return false; } // 逐行使用二分法查找target for (const vector<int>& line : matrix) { if (binarySearch(line, target) != -1) { return true; } } return false; }};

行内 $n$ 个元素做二分查找的时间复杂度为 $O(logn)$ ，共 $m$ 行，故时间复杂度为 $O(mlogn)$ 。

不过上面两种方法似乎都过于直白简单了，考虑到这个题目带的是“中等”tag，肯定还有更高效的算法：

🔗 以下内容来自 LeetCode官方题解

我们可以从矩阵 matrix 的右上角 (0,n−1) 进行搜索。在每一步的搜索过程中，如果我们位于位置 (x,y) ，那么我们希望在以 matrix 的左下角为左下角、以 (x,y) 为右上角的矩阵中进行搜索，即行的范围为 [x,m−1] ，列的范围为 [0,y] ：

• 如果 matrix[x,y]=target ，说明搜索完成
• 如果 matrix[x,y]>target ，由于每一列的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 y 列的元素都是严格大于 target 的，因此我们可以将它们全部忽略，即将 y 减少 1
• 如果 matrix[x,y]<target ，由于每一行的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 x 行的元素都是严格小于 target 的，因此我们可以将它们全部忽略，即将 x 增加 1。

在搜索的过程中，如果我们超出了矩阵的边界，那么说明矩阵中不存在 target 。代码实现如下：

class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int x = 0; int y = matrix[0].size() - 1; while (x < matrix.size() && y >= 0) { if (matrix[x][y] < target) { x++; } else if (matrix[x][y] > target) { y--; } else { return true; } } return false; }};

时间复杂度： $O(m+n)$ 。在搜索的过程中，如果我们没有找到 target ，那么我们要么将 y 减少 1，要么将 x 增加 1。由于 (x,y) 的初始值分别为 (0,n−1) ，因此 y 最多能被减少 n 次， x 最多能被增加 m 次，总搜索次数为 m+n 。在这之后， x 和 y 就会超出矩阵的边界。

148. 排序链表

点此跳转题目链接

题目描述

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

示例 1：

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

示例 2：

输入：head = [-1,5,3,4,0]输出：[-1,0,3,4,5]

示例 3：

输入：head = []输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 104] 内
• -105 <= Node.val <= 105

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

题解

暴力解法无需多言，遍历一遍链表获取全部元素、排序后重新整一个新链表即可：

struct ListNode{ int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {}};class Solution {public: ListNode* sortList(ListNode* head) { vector<int> elements; while (head) { elements.push_back(head->val); head = head->next; } sort(elements.begin(), elements.end()); ListNode *dummyHead = new ListNode(); ListNode *cur = dummyHead; for (int element : elements) { cur->next = new ListNode(element); cur = cur->next; } return dummyHead->next; }};

上述算法时间复杂度为 sort() 的 $O(n\log n)$ ，空间复杂度为 $O(n)$ ——因为新建了一个链表。 直接看看进阶要求：时间复杂度为 $O(n\log n)$ ，空间复杂度为常数级。

考虑算法题中常用的高效排序算法——归并排序，有：

class Solution {public: ListNode *merge(ListNode *L, ListNode *R) { ListNode dummyHead; ListNode *cur = &dummyHead; while (L && R) { if (L->val < R->val) { cur->next = L; L = L->next; } else { cur->next = R; R = R->next; } cur = cur->next; } cur->next = L ? L : R; return dummyHead.next; } ListNode *sortList(ListNode *head, ListNode *tail) { if (!head || head == tail) return head; // 快慢指针找到链表中点 ListNode *slow = head, *fast = head; while (fast != tail && fast->next != tail) { slow = slow->next; fast = fast->next->next; } ListNode *mid = slow->next; slow->next = nullptr; // 断开链表 return merge(sortList(head, slow), sortList(mid, tail)); } ListNode *sortList(ListNode *head) { return sortList(head, nullptr); }};

上述算法时间复杂度为 $O(n\log n)$ ，即归并排序的时间复杂度。空间复杂度取决于递归调用的栈空间，为 $O(\log n)$ ，还是没到最佳的常数级别。为此，需要采用“自底向上”的归并排序实现 $O(1)$ 的空间复杂度：

🔗 以下内容参考 LeetCode官方题解

首先求得链表的长度 length ，然后将链表拆分成子链表进行合并。具体做法如下：

• 用 subLength 表示每次需要排序的子链表的长度，初始时 subLength=1 。
• 每次将链表拆分成若干个长度为 subLength 的子链表（最后一个子链表的长度可以小于 subLength ），按照每两个子链表一组进行合并，合并后即可得到若干个长度为 subLength×2 的有序子链表（最后一个子链表的长度可以小于 subLength×2 ）。合并两个子链表仍然使用之前用过的归并算法。
• 将 subLength 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于 length ，整个链表排序完毕。

通过数学归纳法易证最后得到的链表是有序的（每次合并用到的子链表是有序的，合并后的也是有序的）。

class Solution {public: ListNode *merge(ListNode *L, ListNode *R) { ListNode dummyHead; ListNode *cur = &dummyHead; while (L && R) { if (L->val < R->val) { cur->next = L; L = L->next; } else { cur->next = R; R = R->next; } cur = cur->next; } cur->next = L ? L : R; return dummyHead.next; } ListNode *sortList(ListNode *head) { if (!head) { return nullptr; } // 获取链表长度 int length = 0; ListNode *cur = head; while (cur != nullptr) { length++; cur = cur->next; } // 自底向上，两两合并长度为subLength的子链表 ListNode *dummyHead = new ListNode(0, head); for (int subLength = 1; subLength < length; subLength <<= 1) { ListNode *prev = dummyHead; cur = prev->next; while (cur != nullptr) { // 获取第一个子链表 ListNode *head1 = cur; for (int i = 1; i < subLength && cur->next != nullptr; ++i) {  cur = cur->next; } // 获取第二个子链表 ListNode *head2 = cur->next; cur->next = nullptr; // 断开第一个子链表结尾 cur = head2; for (int i = 1; i < subLength && cur && cur->next; ++i) {  cur = cur->next; } // 预存第三个子链表（即下一轮的第一个子链表）的头节点 // 即第二个子链表结尾节点的next节点 ListNode *nextHead = nullptr; if (cur != nullptr) {  nextHead = cur->next;  cur->next = nullptr; // 断开第二个子链表结尾 } // 合并第一、二个子链表 ListNode *merged = merge(head1, head2); // 更新prev、cur指针 prev->next = merged; while (prev->next != nullptr) {  prev = prev->next; } cur = nextHead; } } return dummyHead->next; }};

该算法时间复杂度为 $O(n\log n)$ ，空间复杂度为 $O(1)$ 。