# 378. 有序矩阵中第 K 小的元素&&373. 查找和最小的 K 对数字（多路并归 优先队列 || 二分查找）(378. The k-th smallest element in the ordered matrix & & 373 Find and minimum k-pair numbers (multiple merge priority queue 𞓜 binary search))-其他

## 378. 有序矩阵中第 K 小的元素&&373. 查找和最小的 K 对数字（多路并归 优先队列 || 二分查找）(378. The k-th smallest element in the ordered matrix & & 373 Find and minimum k-pair numbers (multiple merge priority queue 𞓜 binary search))

### 用例

n == matrix.length
n == matrix[i].length
1 <= n <= 300
-109 <= matrix[i][j] <= 109

1 <= k <= n2

### 思路

``````class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
struct point {
int val, x, y;
point(int val, int x, int y) : val(val), x(x), y(y) {}
bool operator> (const point& a) const { return this->val > a.val; }
};
priority_queue<point, vector<point>, greater<point>> que;
int n = matrix.size();
for (int i = 0; i < n; i++) {
que.emplace(matrix[i][0], i, 0);
}
for (int i = 0; i < k - 1; i++) {
point now = que.top();
que.pop();
if (now.y != n - 1) {
que.emplace(matrix[now.x][now.y + 1], now.x, now.y + 1);
}
}
return que.top().val;
}
};
``````

``````  class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n=matrix.size();
auto count=[&](int x){
int i=0,j=n-1,cnt=0;
while(j>=0&&i<n){
if(matrix[i][j]>x){
j--;
}else{
cnt+=j+1;
i++;
}
}
return cnt;
};
int left=matrix[0][0],right=matrix[n-1][n-1];
while(left<right){
int mid =(right-left)/2+left;
int p=count(mid);
if(p>=k){
right=mid;
}else{
left=mid+1;
}
}
return left;
}
};
``````

### 用例

[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

1 <= nums1.length, nums2.length <= 105
-109 <= nums1[i], nums2[i] <= 109
nums1 和 nums2 均为升序排列
1 <= k <= 1000

### 思路

``````class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int n1=nums1.size(),n2=nums2.size();
vector<vector<int>>ans;
auto cmp=[&](pair<int,int>&a,pair<int,int>&b){if(nums1[a.first]+nums2[a.second]==nums1[b.first]+nums2[b.second]){if(a.first==b.first)return a.second>b.second;else return a.first>b.first;}else return nums1[a.first]+nums2[a.second]>nums1[b.first]+nums2[b.second];};
priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)>pq(cmp);
pq.push({0,0});
int cnt=0;
while(!pq.empty()&&cnt<k){
auto tmp=pq.top();
while(!pq.empty()&&tmp==pq.top()){
pq.pop();
}
int x=tmp.first,y=tmp.second;
ans.push_back({nums1[x],nums2[y]});
cnt++;
if(x+1<n1)pq.push({x+1,y});
if(y+1<n2)pq.push({x,y+1});
}
return ans;
}
};
``````

``````class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
auto cmp = [&nums1, &nums2](const pair<int, int> & a, const pair<int, int> & b) {
return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
};

int m = nums1.size();
int n = nums2.size();
vector<vector<int>> ans;
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
for (int i = 0; i < min(k, m); i++) {
pq.emplace(i, 0);
}
while (k-- > 0 && !pq.empty()) {
auto [x, y] = pq.top();
pq.pop();
ans.emplace_back(initializer_list<int>{nums1[x], nums2[y]});
if (y + 1 < n) {
pq.emplace(x, y + 1);
}
}

return ans;
}
};

``````

``````class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int m = nums1.size();
int n = nums2.size();
auto count = [&](int target){
long long cnt = 0;
int start = 0;
int end = n - 1;
while (start < m && end >= 0) {
if (nums1[start] + nums2[end] > target) {
end--;
} else {
cnt += end + 1;
start++;
}
}
return cnt;
};

/*二分查找第 k 小的数对和的大小*/
int left = nums1[0] + nums2[0];
int right = nums1.back() + nums2.back();
int pairSum = right;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (count(mid) < k) {
left = mid + 1;
} else {
pairSum = mid;
right = mid - 1;
}
}

vector<vector<int>> ans;
int pos = n - 1;
/*找到小于目标值 pairSum 的数对*/
for (int i = 0; i < m; i++) {
while (pos >= 0 && nums1[i] + nums2[pos] >= pairSum) {
pos--;
}
for (int j = 0; j <= pos && k > 0; j++, k--) {
ans.push_back({nums1[i], nums2[j]});
}
}
/*找到等于目标值 pairSum 的数对*/
pos = n - 1;
for (int i = 0; i < m && k > 0; i++) {
while (pos >= 0 && nums1[i] + nums2[pos] > pairSum) {
pos--;
}
for (int j = i; k > 0 && j >= 0 && nums1[j] + nums2[pos] == pairSum; j--, k--) {
ans.push_back({nums1[i], nums2[pos]});
}
}
return ans;
}
};
``````
————————

### subject

Give you a n x n matrix, where the elements of each row and column are sorted in ascending order to find the k-smallest element in the matrix.
Note that it is the k-th smallest element after sorting, not the k-th different element.

### Use case

Example 1:

Input: matrix = [[1,5,9], [10,11,13], [12,13,15]], k = 8
Output: 13
Explanation: the elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th small element is 13
Example 2:

Input: matrix = [[- 5]], k = 1
Output: – 5

Tips:

n == matrix. length
n == matrix[i]. length
1 <= n <= three hundred
-109 <= matrix[i][j] <= one hundred and nine
The topic data ensures that all rows and columns in the matrix are arranged in non decreasing order
1 <= k <= n2

### thinking

< strong > method 1: < / strong > priority queue multi-channel merging
Each row or column is regarded as a chain, with a total of N chains. After that, the minimum value of each chain is input into the priority queue for multiplexing and merging
Every time the priority queue outputs a value, it will cycle through the next value in the linked list into the queue until the k-th value is found

``````class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
struct point {
int val, x, y;
point(int val, int x, int y) : val(val), x(x), y(y) {}
bool operator> (const point& a) const { return this->val > a.val; }
};
priority_queue<point, vector<point>, greater<point>> que;
int n = matrix.size();
for (int i = 0; i < n; i++) {
que.emplace(matrix[i][0], i, 0);
}
for (int i = 0; i < k - 1; i++) {
point now = que.top();
que.pop();
if (now.y != n - 1) {
que.emplace(matrix[now.x][now.y + 1], now.x, now.y + 1);
}
}
return que.top().val;
}
};
``````

< strong > method 2 < / strong > binary search
For all kinds of ordered data structures, they can be transformed by binary search
The upper left corner of the matrix is the minimum value and the lower right corner of the matrix is the maximum value. First, find the middle value between the minimum and maximum values through bisection
Then, count the quantity P in the matrix < strong > not greater than the < / strong > intermediate value, and compare it with the target value K, if P & gt= k. It indicates that ans is less than or equal to the intermediate value mid, so right = mid; If P & lt; K indicates that ans is greater than mid, left = mid + 1;
The counting process can refer to the search for a two-dimensional matrix and count from the upper right corner

``````  class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n=matrix.size();
auto count=[&](int x){
int i=0,j=n-1,cnt=0;
while(j>=0&&i<n){
if(matrix[i][j]>x){
j--;
}else{
cnt+=j+1;
i++;
}
}
return cnt;
};
int left=matrix[0][0],right=matrix[n-1][n-1];
while(left<right){
int mid =(right-left)/2+left;
int p=count(mid);
if(p>=k){
right=mid;
}else{
left=mid+1;
}
}
return left;
}
};
``````

### subject

Given two integer arrays nums1 and nums2 arranged in ascending order, and an integer K.

Define a pair of values (U, V), where the first element is from nums1 and the second element is from nums2.

Please find the minimum number of K} pairs (U1, V1), (U2, V2)  (uk,vk) 。

### Use case

Example 1:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [1,2], [1,4], [1,6]
Explanation: returns the first 3 logarithms in the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
Example 2:

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [1,1], [1,1]
Explanation: returns the first two logarithms in the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
Example 3:

Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [1,3], [2,3]
Explanation: it is also possible that all pairs in the sequence are returned: [1,3], [2,3]

Tips:

1 <= nums1.length, nums2.length <= 105
-109 <= nums1[i], nums2[i] <= 109
nums1 和 nums2 均为升序排列
1 <= k <= 1000

### thinking

< strong > method 1 < / strong > multi channel merging
Put the sequence of the sum of each number in nums1 [0] and nums2 into the priority queue, arrange it according to the size of sum, and then multiplex and merge
I wrote a single team directly, so there is still a problem of de duplication

``````class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int n1=nums1.size(),n2=nums2.size();
vector<vector<int>>ans;
auto cmp=[&](pair<int,int>&a,pair<int,int>&b){if(nums1[a.first]+nums2[a.second]==nums1[b.first]+nums2[b.second]){if(a.first==b.first)return a.second>b.second;else return a.first>b.first;}else return nums1[a.first]+nums2[a.second]>nums1[b.first]+nums2[b.second];};
priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)>pq(cmp);
pq.push({0,0});
int cnt=0;
while(!pq.empty()&&cnt<k){
auto tmp=pq.top();
while(!pq.empty()&&tmp==pq.top()){
pq.pop();
}
int x=tmp.first,y=tmp.second;
ans.push_back({nums1[x],nums2[y]});
cnt++;
if(x+1<n1)pq.push({x+1,y});
if(y+1<n2)pq.push({x,y+1});
}
return ans;
}
};
``````

After optimization and elimination of duplication

``````class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
auto cmp = [&nums1, &nums2](const pair<int, int> & a, const pair<int, int> & b) {
return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
};

int m = nums1.size();
int n = nums2.size();
vector<vector<int>> ans;
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
for (int i = 0; i < min(k, m); i++) {
pq.emplace(i, 0);
}
while (k-- > 0 && !pq.empty()) {
auto [x, y] = pq.top();
pq.pop();
ans.emplace_back(initializer_list<int>{nums1[x], nums2[y]});
if (y + 1 < n) {
pq.emplace(x, y + 1);
}
}

return ans;
}
};

``````

< strong > method 2 < / strong > binary search
Ibid

``````class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int m = nums1.size();
int n = nums2.size();
auto count = [&](int target){
long long cnt = 0;
int start = 0;
int end = n - 1;
while (start < m && end >= 0) {
if (nums1[start] + nums2[end] > target) {
end--;
} else {
cnt += end + 1;
start++;
}
}
return cnt;
};

/*二分查找第 k 小的数对和的大小*/
int left = nums1[0] + nums2[0];
int right = nums1.back() + nums2.back();
int pairSum = right;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (count(mid) < k) {
left = mid + 1;
} else {
pairSum = mid;
right = mid - 1;
}
}

vector<vector<int>> ans;
int pos = n - 1;
/*找到小于目标值 pairSum 的数对*/
for (int i = 0; i < m; i++) {
while (pos >= 0 && nums1[i] + nums2[pos] >= pairSum) {
pos--;
}
for (int j = 0; j <= pos && k > 0; j++, k--) {
ans.push_back({nums1[i], nums2[j]});
}
}
/*找到等于目标值 pairSum 的数对*/
pos = n - 1;
for (int i = 0; i < m && k > 0; i++) {
while (pos >= 0 && nums1[i] + nums2[pos] > pairSum) {
pos--;
}
for (int j = i; k > 0 && j >= 0 && nums1[j] + nums2[pos] == pairSum; j--, k--) {
ans.push_back({nums1[i], nums2[pos]});
}
}
return ans;
}
};
``````