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))

链接:https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/

题目

给你一个 n x n 矩阵 matrix ,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。
请注意,它是 排序后 的第 k 小元素,而不是第 k 个 不同 的元素。

用例

示例 1:

输入:matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出:13
解释:矩阵中的元素为 [1,5,9,10,11,12,13,13,15],第 8 小元素是 13
示例 2:

输入:matrix = [[-5]], k = 1
输出:-5

提示:

n == matrix.length
n == matrix[i].length
1 <= n <= 300
-109 <= matrix[i][j] <= 109
题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
1 <= k <= n2

思路

方法一:优先队列 多路并归
每行或者每列看成一条链 一共有n条链 让后将每条链最小值输入优先队列 做多路并归
优先队列每输出一个值 将这个值在链表中的下一个值输入队列中 循环直到找到第k个值

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;
    }
};

方法二二分查找
对于各种有序的数据结构,都可以通过二分查找变形来
矩阵左上角为最小值,矩阵右下角为最大值,先通过二分寻找最小最大值之间的中间值
然后计数矩阵中不大于中间值的数量p ,与目标值k进行比较,如果p>=k,说明ans小于等于中间值mid,因此right=mid;如果p<k说明ans大于mid,left=mid+1;
计数过程可以参考搜索二维矩阵从右上角开始计数

  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;
    }
};

类似题:

链接:https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/solution/cha-zhao-he-zui-xiao-de-kdui-shu-zi-by-l-z526/

题目

给定两个以 升序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  …  (uk,vk) 。

用例

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数:
  [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
示例 3:

输入: nums1 = [1,2], nums2 = [3], k = 3
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]

提示:

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

思路

方法一多路并归
将nums1[0]与nums2中每一个数字的和的序列放入优先队列 按照和的大小排列 然后多路并归
我写的单个直接入队所以还存在去重问题

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;
    }
};
————————

链接:https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/

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;
    }
};

Similar questions:

链接:https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/solution/cha-zhao-he-zui-xiao-de-kdui-shu-zi-by-l-z526/

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;
    }
};