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:vector<int> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {int n1 = nums1.size(), n2 = nums2.size();priority_queue<tuple<int, int, int>> pq;vector<int> 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 = get<1>(t), j = get<2>(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(vector<vector<int>>& mat, int k) {int n = mat.size();vector<int> 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,且多個條件i+j!=n-1

代碼

c++:

class Solution {
public:vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {int n = arr.size();vector<int> arr2 = arr;vector<vector<int>> res;reverse(arr2.begin(), arr2.end());priority_queue<tuple<double, 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 = get<1>(t), j = get<2>(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();}
};