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;}// 逐行使用二分法查找targetfor (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)$ 。