北京网站建设亿玛酷专注4,简单企业网站模板,平台型网站如何推广,如何搜索公司所有的网站目录 240. 搜索二维矩阵 II题目描述题解 148. 排序链表题目描述题解 240. 搜索二维矩阵 II
点此跳转题目链接
题目描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性#xff1a;
每行的元素从左到右升序排列。每列的元素从上到… 目录 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.lengthn matrix[i].length1 n, m 300-109 matrix[i][j] 109每行的所有元素从左到右升序排列每列的所有元素从上到下升序排列-109 target 109
题解
暴力算法直接遍历整个矩阵时间复杂度为 O ( m n ) O(mn) O(mn) m 、 n m、n m、n 分别为矩阵的行、列数。
由于题中矩阵在行和列上的元素都是升序的所以想到可以从上到下逐行利用二分查找解决
class Solution {
public:int binarySearch(const vectorint 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(vectorvectorint matrix, int target) {if (matrix.empty()) {return false;}// 逐行使用二分法查找targetfor (const vectorint line : matrix) {if (binarySearch(line, target) ! -1) {return true;}}return false;}
};行内 n n n 个元素做二分查找的时间复杂度为 O ( l o g n ) O(logn) O(logn) 共 m m m 行故时间复杂度为 O ( m l o g n ) O(mlogn) 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(vectorvectorint 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 ) O(mn) O(mn) 。在搜索的过程中如果我们没有找到 target 那么我们要么将 y 减少 1要么将 x 增加 1。由于 (x,y) 的初始值分别为 (0,n−1) 因此 y 最多能被减少 n 次 x 最多能被增加 m 次总搜索次数为 mn 。在这之后 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) {vectorint 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\log{n}) O(nlogn) 空间复杂度为 O ( n ) O(n) O(n) ——因为新建了一个链表。 直接看看进阶要求时间复杂度为 O ( n log n ) O(n\log{n}) O(nlogn) 空间复杂度为常数级。
考虑算法题中常用的高效排序算法——归并排序有
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(n\log{n}) O(nlogn) 即归并排序的时间复杂度。空间复杂度取决于递归调用的栈空间为 O ( log n ) O(\log{n}) O(logn) 还是没到最佳的常数级别。为此需要采用“自底向上”的归并排序实现 O ( 1 ) O(1) O(1) 的空间复杂度 以下内容参考 LeetCode官方题解 首先求得链表的长度 length 然后将链表拆分成子链表进行合并。具体做法如下
用 subLength 表示每次需要排序的子链表的长度初始时 subLength1 。每次将链表拆分成若干个长度为 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(n \log{n}) O(nlogn) 空间复杂度为 O ( 1 ) O(1) O(1) 。
