鞍山市建设局网站,东莞热的建设网站,赵县网站建设,网站建设需要哪些费用支出题目传送门 主要看灵神的二分模版#xff0c;如何使用递归实现在 O ( m k ) O(mk) O(mk)时间内#xff0c;实现对于二分中每个条件的判断。 一般套路#xff1a;
dfs函数返回值为布尔类型
循环中使用一个dfs#xff0c;如果其返回true#xff0c;那么直接这个dfs返回tru…题目传送门 主要看灵神的二分模版如何使用递归实现在 O ( m k ) O(mk) O(mk)时间内实现对于二分中每个条件的判断。 一般套路
dfs函数返回值为布尔类型
循环中使用一个dfs如果其返回true那么直接这个dfs返回true
技巧 一个引用类型的值作为终止条件的判断所有的dfs共享这个变量。 灵神代码
class Solution {// 返回是否找到 k 个子数组和bool dfs(vectorvectorint mat, int left_k, int i, int s) {if (i 0) // 能递归到这里说明数组和不超过二分的 midreturn --left_k 0; // 是否找到 k 个for (int x: mat[i]) { // 「枚举选哪个」注意 mat[i] 是有序的if (x - mat[i][0] s) // 选 x 不选 mat[i][0]break; // 剪枝后面的元素更大无需枚举if (dfs(mat, left_k, i - 1, s - (x - mat[i][0]))) // 选 x 不选 mat[i][0]return true; // 找到 k 个就一直返回 true不再递归}return false;}public:int kthSmallest(vectorvectorint mat, int k) {int sl 0, sr 0;for (auto row: mat) {sl row[0];sr row.back();}// 二分模板 https://www.bilibili.com/video/BV1AP41137w7/int left sl - 1, right sr; // 开区间 (sl-1,sr)while (left 1 right) { // 开区间不为空// 循环不变量// f(left) k// f(right) kint mid left (right - left) / 2;int left_k k;if (dfs(mat, left_k, mat.size() - 1, mid - sl)) // 先把第一列的所有数都选上right mid; // 二分范围缩小至开区间 (left, mid)else // f(mid) kleft mid; // 二分范围缩小至开区间 (mid, right)}return right;}
};作者灵茶山艾府
链接https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/solutions/2286593/san-chong-suan-fa-bao-li-er-fen-da-an-du-k1vd/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
时间复杂度思考 为什么回溯的时间复杂度为 O ( m k ) O(mk) O(mk)dfs递归的过程是一棵树从顶到底本题中如果能够递归到 i 0 i0 i0那么就是走完了一条路径该路径花费时间 O ( m k ) O(mk) O(mk)。如果能够成功走完k条路径那么就直接所有的dfs开始统一返回true在此之前所有的dfs返回的都是false。 这样做的好处是虽然每个dfs中的for循环还没结束但是由于出现了一个true,提前终止了循环所有就可以保证递归树中每一层的节点个数最多为k个。着实神奇而且写法十分优雅
