小企业建网站,关闭WordPress自动文章摘要,易讯网站建设,百度搜索热度查询7. 1439.有序矩阵中的第K个最小数组和(困难,学习转化为373)
1439. 有序矩阵中的第 k 个最小数组和 - 力扣#xff08;LeetCode#xff09;
思想
1.给你一个 m * n 的矩阵 mat#xff0c;以及一个整数 k #xff0c;矩阵中的每一行都以非递减的顺序排列。 你可以从每一行…7. 1439.有序矩阵中的第K个最小数组和(困难,学习转化为373)
1439. 有序矩阵中的第 k 个最小数组和 - 力扣LeetCode
思想
1.给你一个 m * n 的矩阵 mat以及一个整数 k 矩阵中的每一行都以非递减的顺序排列。 你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。 2.转化为373.查找和最小的K对数字利用最小堆373是从两个数组找前K个而此题是m*n矩阵但是发现假设已经取完矩阵前两行的数组和再考虑第3行时只要考虑前两行数组前K个值即可(因为后面的不可能是最终的K个最小数组和)所以问题就转化为得到前面i-1行的最小K个数组和数组然后第i行考虑进来最终再得到一个最小K个数组和数组实现行的压缩 3.初始数组为只有0元素的数组和第一行(表示取第一行前K个元素)
代码
c:
class Solution {
public:vectorint kSmallestPairs(vectorint nums1, vectorint nums2, int k) {int n1 nums1.size(), n2 nums2.size();priority_queuetupleint, int, int pq;vectorint res;for (int i 0; i min(n1, k); i) {pq.emplace(-nums1[i] - nums2[0], i,0); }while (!pq.empty() res.size() k) {auto t pq.top();pq.pop();int i get1(t), j get2(t);res.push_back(nums1[i] nums2[j]);if (j 1 n2)pq.emplace(-nums1[i] - nums2[j 1], i,j 1); }return res;}int kthSmallest(vectorvectorint mat, int k) {int n mat.size();vectorint ini {0};for (auto row : mat) {ini kSmallestPairs(row, ini, k);}return ini.back();}
};8. 786. 第K个最小的质数分数(中等)
思想
1.给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 质数 组成且其中所有整数互不相同。 对于每对满足 0 i j arr.length 的 i 和 j 可以得到分数 arr[i] / arr[j] 。 那么第 k 个最小的分数是多少呢? 以长度为 2 的整数数组返回你的答案, 这里 answer[0] arr[i] 且 answer[1] arr[j] 。 2.依旧转化为373.查找和最小的K对数字,只不过nums2是倒序的arr,且多个条件ij!n-1
代码
c:
class Solution {
public:vectorint kthSmallestPrimeFraction(vectorint arr, int k) {int n arr.size();vectorint arr2 arr;vectorvectorint res;reverse(arr2.begin(), arr2.end());priority_queuetupledouble, int, int pq;for (int i 0; i min(n - 1, k); i)pq.emplace(-1.0 * arr[i] / arr2[0], i, 0);while (res.size() k !pq.empty()) {auto t pq.top();pq.pop();int i get1(t), j get2(t);if (i j n - 1)continue;res.push_back({arr[i], arr2[j]});if (j 1 n)pq.emplace(-1.0 * arr[i] / arr2[j 1], i, j 1);}return res.back();}
};
