378. Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
return 13.

S1: min heap O(klogk)

对于任意矩阵元素，它的下一个最小的元素一定在它的右方或下方。从整个矩阵开始的元素matrix[0][0]开始，维护一个最小堆，重复下列操作k-1次：

1. 取出堆顶元素
2. 将堆顶元素右边和下面的元素入堆

删除了k-1次最小元素后，堆顶元素即为第k小元素。

因为需要知道堆里元素的坐标，用node struct来存储元素值和坐标。priority_queue默认为最大堆，需要重新定义comparator。

class Solution {
public:
    /**
     * @param matrix: a matrix of integers
     * @param k: an integer
     * @return: the kth smallest number in the matrix
     */
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        priority_queue<Node, vector<Node>, cmp> minHeap;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        minHeap.push(Node(0, 0, matrix[0][0]));
        vector<int> dx{0, 1};
        vector<int> dy{1, 0};
        for (int i = 0; i < k - 1; ++i) {
            Node cur = minHeap.top();
            minHeap.pop();
            for (int j = 0; j < 2; ++j) {
                int x = cur.x + dx[j];
                int y = cur.y + dy[j];
                if (x < m && y < n && !visited[x][y]) {
                    visited[x][y] = true;
                    minHeap.push(Node(x, y, matrix[x][y]));
                }
            }
        }
        return minHeap.top().val;
    }

private:
    struct Node {
        int x;
        int y;
        int val;
        Node(int x, int y, int val): x(x), y(y), val(val) {}
    };
    struct cmp {
        bool operator() (const Node& a, const Node& b) const {
            return a.val > b.val;
        }
    };
};

373. Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

S1: min heap O(k(logk))

nums1作纵坐标， nums2作纵坐标，他们的合形成矩阵，就是Kth Smallest Element in a Sorted Matrix。此题sum换成product也是一样的解法。

class Solution {
public:
    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size();
        int n = nums2.size();
        vector<pair<int, int>> result;
        priority_queue<Node, vector<Node>, cmp> queue;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<int> dx{0, 1};
        vector<int> dy{1, 0};
        if (m < 1 || n < 1) {
            return result;
        }

        queue.push(Node(0, 0, nums1[0] + nums2[0]));
        for (int i = 0; i < k  && !queue.empty(); ++i) {
            Node cur = queue.top();
            result.push_back(pair<int, int>{nums1[cur.x], nums2[cur.y]});
            queue.pop();
            for (int j = 0; j < 2; ++j) {
                int x = cur.x + dx[j];
                int y = cur.y + dy[j];
                if (x < m && y < n && !visited[x][y]) {
                    int sum = nums1[x] + nums2[y];
                    queue.push(Node(x, y, sum));
                    visited[x][y] = true;
                }
            }
        }
        return result;
    }
private:
    struct Node {
        int x;
        int y;
        int val;
        Node(int x, int y, int val): x(x), y(y), val(val) {}
    };
    struct cmp {
        bool operator() (const Node& a, const Node& b) const {
            return a.val > b.val;
        }
    }; 
};