【Day 89 】2022-03-10 - 378. 有序矩阵中第 K 小的元素

[azl397985856]

378. 有序矩阵中第 K 小的元素

入选理由

暂无

题目地址

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

前置知识

• 二分查找
• 堆

  题目描述

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

 

示例：

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

返回 13。  

提示： 你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。

[feifan-bai]

思路 1.从左上到右下数字递增，二分查找有序队列，减少时间成本

代码

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        def check(mid):
            i, j = n-1, 0
            num = 0
            while i >= 0 and j < n:
                if matrix[i][j] <= mid:
                    num += i+1
                    j += 1
                else:
                    i -= 1
            return num >= k

        l, r = matrix[0][0], matrix[-1][-1]
        while l < r:
            mid = (l + r) // 2
            if check(mid):
                r = mid
            else:
                l = mid+1
        return l

复杂度分析

• 时间复杂度：O(Nlog(r-l))
• 空间复杂度：O(1)

[rzhao010]

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int row = matrix.length;
        int col = matrix[0].length;
        int left = matrix[0][0];
        int right = matrix[row - 1][col - 1];
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = findNotBiggerThanMid(matrix, mid, row, col);
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }

    private int findNotBiggerThanMid(int[][] matrix, int mid, int row, int col) {
        int i = row - 1;
        int j = 0;
        int count = 0;
        while (i >= 0 && j < col) {
            if (matrix[i][j] <= mid) {
                // in col j, i + 1 numbers <= mid
                count += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return count;
    }
}

[cszys888]

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        l, r = matrix[0][0], matrix[n - 1][n - 1]

        def binary_search(m):
            row, col = n - 1, 0
            count = 0
            value = float('-inf')
            while row >= 0 and col <= n - 1:
                if matrix[row][col] <= m:
                    value = max(value, matrix[row][col])
                    count += row + 1
                    col += 1
                else:
                    row -= 1
            return count, value

        while l <= r:
            m = (l + r) // 2
            count, value = binary_search(m)
            if count == k:
                return value
            elif count < k:
                l = m + 1
            else:
                r = m - 1

        return l

time complexity: O(n*log(r - l)) where r, l stand for maximum and minimum value in matrix space complexity: O(1)

[zhangzz2015]

• 有两种解法，1种采用heap。另外一种采用bindary search。用heap实现code量要少一些，时间复杂度为O(ｋlogｎ)，空间复杂度为 Ｏ（ｎ）．

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        ///  Start heap.  or binary search. 
        // Time O(klogn)  Space O(k)    
        //  Time: 4:36. 
        int row = matrix.size();
        auto comp = [](vector<int>& node1, vector<int>& node2)
        {
           if(node1[0]==node2[0]) return node1[1]>node2[1]; 
            return node1[0]>node2[0]; 

        }; 
        priority_queue<vector<int>, vector<vector<int>>, decltype(comp)> pq(comp);
        for(int i=0; i< row; i++ )
        {
            pq.push({matrix[i][0], i, 0}); 
        }
        k--; 
        while(k)
        {
            auto it = pq.top(); 
            pq.pop();     
            if(it[2]+1<row)
            {
                pq.push({matrix[it[1]][it[2]+1], it[1], it[2]+1}); 
            }
            k--; 
        }
        return pq.top()[0]; 

    }
};

[yan0327]

func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)
    l,r :=matrix[0][0],matrix[n-1][n-1]
    for l < r{
        mid := l + (r-l)>>1
        if isValid(matrix,mid,k){
            l = mid+1
        }else{
            r = mid
        }
    }
    return l
}
func isValid(matrix [][]int,mid int,k int) bool{
    total := 0
    row,col := len(matrix)-1,0
    for row>=0&&col<len(matrix){
        for row>=0&&matrix[row][col] > mid{
            row--
        }
        total += row+1
        col++
    }
    return total < k
}

[xuhzyy]

class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        n = len(matrix)
        h = []
        h.append([matrix[0][0], 0, 0])
        matrix[0][0] = float('inf')
        for _ in range(k):
            num, i, j = heapq.heappop(h)
            if i + 1 < n and matrix[i+1][j] < float('inf'):
                heapq.heappush(h, [matrix[i+1][j], i+1, j])
                matrix[i+1][j] = float('inf')
            if j + 1 < n and matrix[i][j+1] < float('inf'):
                heapq.heappush(h, [matrix[i][j+1], i, j+1])
                matrix[i][j+1] = float('inf')
        return num

[ZacheryCao]

Idea

Min heap

Code

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        N = len(matrix)
        heap = []
        for i in range(min(N, k)):
            heap.append((matrix[i][0], i, 0))
        heapq.heapify(heap)
        while k:
            value, row, col = heapq.heappop(heap)
            if col<N-1:
                heapq.heappush(heap, (matrix[row][col+1],row, col+1))
            k-=1
        return value

Complexity:

Time: O(min(N, k)+Klog(min(N,k)) Space: O(min(N,k)

[ivangin]

code

public class KthSmallestElementinaSortedMatrix {

    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left + 1 < right) {
            int mid = (right - left) / 2 + left;
            int num = count(matrix, mid);
            if (num >= k) right = mid;
            else left = mid;
        }
        if (count(matrix, right) <= k - 1) return right;
        return left;
    }

    private int count(int[][] matrix, int target) {
        int n = matrix.length;
        int res = 0;
        int i = n - 1, j = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] < target) {
                res += i + 1;
                j++;
            } else i--;
        }
        return res;
    }
}

[ZJP1483469269]

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        def check(mid):
            y , x = n-1 , 0
            cnt = 0

            while x < n and y >= 0:
                if matrix[y][x] <= mid:
                    x += 1
                    cnt += (y + 1)
                else:
                    y -= 1
            return cnt >= k

        l , r = min(min(matrix)) , max(max(matrix))

        while l < r:
            mid = l + r >> 1
            if check(mid) :
                r = mid
            else:
                l = mid + 1

        return l

[1149004121]

378. 有序矩阵中第 K 小的元素

思路

因为矩阵是有序的，考虑用二分法。

代码

var kthSmallest = function(matrix, k) {
    const n = matrix.length;
    let left = matrix[0][0], right = matrix[n - 1][n - 1];
    while(left < right){
        let mid = (left + right) >> 1;
        if(check(mid)){
            right = mid;
        }else{
            left = mid + 1;
        }
    };
    return left;

    function check(value){
        let i = n - 1, j = 0;
        let count = 0;
        while(i >= 0 && j < n){
            if(matrix[i][j] <= value){
                count += i + 1;
                j++;
            }else{
                i--;
            }
        };
        return count >= k;
    }
};

复杂度分析

• 时间复杂度：O( N*log(r - l) ) 。
• 空间复杂度：O(1) 。

[haixiaolu]

思路

小根堆

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        # The size of the matrix
        N = len(matrix)

        # preparing our min-heap
        minHeap = []
        for r in range(min(k, N)):
            # we add triplets of information for each cell
            minHeap.append((matrix[r][0], r, 0))

        # heapify our list
        heapq.heapify(minHeap)

        # until we find k elements
        while k:
            # extract -min 
            element, r, c = heapq.heappop(minHeap)

            # if we have any new elements in the current row, add them
            if c < N - 1:
                heapq.heappush(minHeap, (matrix[r][c + 1], r, c + 1))

            # Decrement K
            k -= 1

        return element 

[wangzehan123]

代码

• 语言支持：Java

Java Code:

public class Solution {
    private class Node{
        int x,y,v;
        Node(int x, int y, int v){
            this.x = x; this.y = y; this.v = v;
        }
    }
    public int kthSmallest(int[][] M, int k) {
        PriorityQueue<Node> q = new PriorityQueue<>(Comparator.comparing((Node n)->n.v ));
        int count = 0;
        int[] dx = {0,1}, dy = {1,0};
        int ans = 0;
        int n = M.length, m = M[0].length;
        boolean[][] visited = new boolean[n][m];
        q.add(new Node(0,0,M[0][0] ));
        visited[0][0] = true;
        while(count < k){
            Node p = q.poll();
            for(int i= 0; i<2;i++){
                int x = p.x+dx[i];
                int y = p.y+dy[i];
                if(x>=0 && x<n && y>=0 && y<m && !visited[x][y]){
                    q.offer(new Node(x, y, M[x][y]));
                    visited[x][y] =true;
                }
            }
            ans = p.v;
            count++;
        }
        return ans;
    }
}

[Tesla-1i]

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        N = len(matrix)
        heap = []
        for i in range(min(N, k)):
            heap.append((matrix[i][0], i, 0))
        heapq.heapify(heap)
        while k:
            value, row, col = heapq.heappop(heap)
            if col<N-1:
                heapq.heappush(heap, (matrix[row][col+1],row, col+1))
            k-=1
        return value

[yetfan]

思路 二分

代码

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)

        def check(mid):
            i, j = n - 1, 0
            num = 0
            while i >= 0 and j < n:
                if matrix[i][j] <= mid:
                    num += i + 1
                    j += 1
                else:
                    i -= 1
            return num >= k

        left, right = matrix[0][0], matrix[-1][-1]
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1

        return left

复杂度 时间 O(nlog(r-l)) 空间 O(1)

[LannyX]

思路

PQ

代码

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> matrix[a[0]][a[1]] - matrix[b[0]][b[1]]);
        int n = matrix.length;
        for(int i = 0; i < n; i++){
            pq.offer(new int[]{i, 0});
        }
        while(k > 1){
            int[] min = pq.poll();
            int x = min[0], y = min[1] + 1;
            if(y < n){
                pq.offer(new int[]{x, y});
            }            
            k--;

        }
        int[] min = pq.poll();
        return matrix[min[0]][min[1]];
    }
}

[KennethAlgol]

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int rows = matrix.length, columns = matrix[0].length;
        int[] sorted = new int[rows * columns];
        int index = 0;
        for (int[] row : matrix) {
            for (int num : row) {
                sorted[index++] = num;
            }
        }
        Arrays.sort(sorted);
        return sorted[k - 1];
    }
}

[falconruo]

思路: 方法一、MaxHeap 方法二、Binary Search

复杂度分析: 方法二、 时间复杂度: O(n * log(r - l)), n, m为矩阵matrix的行元素个数, log(r - l)为二分查找 空间复杂度: O(1)

代码(C++):

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size() - 1;
        int l = matrix[0][0];
        int r = matrix[n][n];

        while (l <= r) {
            int m = l + (r - l) / 2;
            int cnt = 0;
            int row = 0;
            int col = n;

            while (col >= 0 && row <= n) {
                if (matrix[row][col] <= m) {
                    cnt += col + 1; // n + 1 element each row
                    row++;
                } else
                    col--;
            }

            if (cnt >= k)
                r = m - 1;
            else
                l = m + 1;
        }

        return l;
    }
};

[callmeerika]

思路

二分查找

代码

var check = function (matrix, mid, k, n) {
  let i = n - 1;
  let j = 0;
  let num = 0;
  while (i >= 0 && j < n) {
    if (matrix[i][j] <= mid) {
      num += i + 1;
      j++;
    } else {
      i--;
    }
  }
  return num >= k;
};

var kthSmallest = function (matrix, k) {
  let n = matrix.length;
  let left = matrix[0][0];
  let right = matrix[n - 1][n - 1];
  while (left < right) {
    let mid = left + ((right - left) >> 1);
    if (check(matrix, mid, k, n)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
};

复杂度

时间复杂度：O(nlog(r-l))
空间复杂度：O(1)

[watchpoints]

//https://github.com/wisdompeak/LeetCode/tree/master/Priority_Queue/378.Kth-Smallest-Element-in-a-Sorted-Matrix
//https://github.com/guanjunjian/LeetCode/blob/master/Solution/378.%E6%9C%89%E5%BA%8F%E7%9F%A9%E9%98%B5%E4%B8%AD%E7%AC%ACK%E5%B0%8F%E7%9A%84%E5%85%83%E7%B4%A0.md

class Solution
{
public:
    //仿函数
    struct compare
    {
        bool operator()(pair<int, pair<int, int>> &p1, pair<int, pair<int, int>> &p2)
        {
            // “大于” 构造的是最小堆
            return p1.first > p2.first;
        }
    };
    int kthSmallest(vector<vector<int>> &matrix, int k)
    {
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, compare> pq;
        int cols, rows;
        rows = matrix.size();
        cols = matrix[0].size();
        //将每一行的第0列入队
        for (int i = 0; i < rows; ++i)
            pq.push(make_pair(matrix[i][0], make_pair(i, 0)));

        int res = 0;
        while (k)
        {
            res = pq.top().first;
            //记录堆顶元素所在的行、列
            int r = pq.top().second.first;
            int c = pq.top().second.second;
            pq.pop();
            --k;
            if (c + 1 < cols)
                pq.push(make_pair(matrix[r][c + 1], make_pair(r, c + 1)));
        }
        return res;
    }
};

class Solution2
{
public:
    int kthSmallest(vector<vector<int>> &matrix, int k)
    {
        auto comp = [&matrix](pair<int, int> p1, pair<int, int> p2) {
            return matrix[p1.first][p1.second] > matrix[p2.first][p2.second];
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> que(comp);
        que.push(make_pair(0, 0));
        int count = 1;
        while (count < k)
        {
            auto temp = que.top();
            que.pop();
            cout << "temp.first= " << temp.first << " temp.second " << temp.second << " value= " << matrix[temp.first][temp.second] << endl;
            if (temp.first + 1 < matrix.size())
            {
                que.push(make_pair(temp.first + 1, temp.second));
            }
            //if (temp.first == 0 && temp.second + 1 < matrix[0].size())
            if (temp.first == 0 && temp.second + 1 < matrix[0].size())
            {
                que.push(make_pair(temp.first, temp.second + 1));
            }
            count++;
        }
        auto t = que.top();
        return matrix[t.first][t.second];
    }

    /***  次方法虽然秒，但是我看不懂，并且体会里面好出，为什么大家都这样做。
      *  利用题目给出条件：有序  采用二分查找。
      *  
      *  二分查找关键 最大值，最小值,和中间值（卡住了）
      *  求top k  k是索引。array{k} ==中间值
      *  
      * 时间复杂度其实也是很高的
      * 1.找出二维矩阵中最小的数left，最大的数right，那么第k小的数必定在left~right之间
        2.mid=(left+right) / 2；在二维矩阵中寻找小于等于mid的元素个数count
        3.若这个count小于k，表明第k小的数在右半部分且不包含mid，即left=mid+1, right=right，又保证了第k小的数在left~right之间
        4.若这个count大于k，表明第k小的数在左半部分且可能包含mid，即left=left, right=mid，又保证了第k小的数在left~right之间
        5.因为每次循环中都保证了第k小的数在left~right之间，当left==right时，第k小的数即被找出，等于right 
          (76 ms ）
      */
    int kthSmallest1(vector<vector<int>> &matrix, int k)
    {
        int rows = matrix.size();
        if (0 == rows)
            return -1; //不存在
        int cols = matrix[0].size();
        //1 5 9 10 11 11 12 13 13 15
        // k=8 13
        // matrix = [
        //     *⁠[1, 5, 9],
        //     *⁠[10, 11, 13],
        //     *⁠[12, 13, 15] *
        // ],
        int low = matrix[0][0];
        int high = matrix[rows - 1][cols - 1];

        int mid = 0; //中间数值，array中是不存在的，通过计算是否第k小，变化low 和high的范围。

        while (low < high)
        {
            cout << low << "aaa" << mid << " " << high << endl;
            mid = low + (high - low) / 2;
            int count = findNotBiggerThanMid(matrix, mid);
            if (k > count)
            {
                low = mid + 1; //此时 low 变成可能不存。
            }
            else
            {
                high = mid;
            }
            cout << low << "bbb" << mid << " " << high << endl;
        }

        return low;
    }
    //查找一个元素
    int findNotBiggerThanMid(vector<vector<int>> &matrix, int x)
    {
        int N = matrix.size();
        int i = N - 1, j = 0, count = 0;
        while (i >= 0 && j < N)
        {
            if (matrix[i][j] <= x)
            {
                count += (i + 1);
                //排除列
                j++;
            }
            else
                //排除行
                i--;
        }
        return count;
    }
};

[moirobinzhang]

Code:

public class Solution { public int KthSmallest(int[][] matrix, int k) {

    int leftnum = matrix[0][0];
    int rightnum = matrix[matrix.Length - 1][matrix[0].Length - 1];

    while (leftnum <= rightnum)
    {
        int midnum = (rightnum - leftnum) / 2 + leftnum;
        int count = GetNotBiggerCount(matrix, midnum);

        if (count < k)
            leftnum = midnum + 1;
        else
            rightnum = midnum - 1;           

    }

    return leftnum; 
}

public int GetNotBiggerCount(int[][] matrix, int midNum)
{
    int col = 0;
    int row = matrix.Length - 1;
    int count = 0;

    while (row >= 0 & col < matrix[0].Length)
    {
        if (matrix[row][col] > midNum)
            row--;
        else
        {
            count += row + 1;
            col++;
        }
    }

    return count;        
}

}

[Aobasyp]

思路 二分查找

function notGreaterCount(matrix, target) { // 等价于在matrix 中搜索mid，搜索的过程中利用有序的性质记录比mid小的元素个数

// 我们选择左下角，作为开始元素 let curRow = 0; // 多少列 const COL_COUNT = matrix[0].length; // 最后一列的索引 const LAST_COL = COL_COUNT - 1; let res = 0;

while (curRow < matrix.length) { // 比较最后一列的数据和target的大小 if (matrix[curRow][LAST_COL] < target) { res += COL_COUNT; } else { let i = COL_COUNT - 1; while (i < COL_COUNT && matrix[curRow][i] > target) { i--; } // 注意这里要加1 res += i + 1; } curRow++; }

return res; }

var kthSmallest = function (matrix, k) { if (matrix.length < 1) return null; let start = matrix[0][0]; let end = matrix[matrix.length - 1][matrix[0].length - 1]; while (start < end) { const mid = start + ((end - start) >> 1); const count = notGreaterCount(matrix, mid); if (count < k) start = mid + 1; else end = mid; } // 返回start,mid, end 都一样 return start; };

时间复杂度：O(nlog(r-l)) 空间复杂度：O(1)

[guangsizhongbin]

func kthSmallest(matrix [][]int, k int) int { rows, columns := len(matrix), len(matrix[0]) sorted := make([]int, rows * columns) index := 0 for , row := range matrix { for , num := range row { sorted[index] = num index++ } } sort.Ints(sorted) return sorted[k-1] }

[Hacker90]

Code:

public class Solution { public int KthSmallest(int[][] matrix, int k) {

int leftnum = matrix[0][0];
int rightnum = matrix[matrix.Length - 1][matrix[0].Length - 1];

while (leftnum <= rightnum)
{
    int midnum = (rightnum - leftnum) / 2 + leftnum;
    int count = GetNotBiggerCount(matrix, midnum);

    if (count < k)
        leftnum = midnum + 1;
    else
        rightnum = midnum - 1;           

}

return leftnum; 

}

public int GetNotBiggerCount(int[][] matrix, int midNum) { int col = 0; int row = matrix.Length - 1; int count = 0;

while (row >= 0 & col < matrix[0].Length)
{
    if (matrix[row][col] > midNum)
        row--;
    else
    {
        count += row + 1;
        col++;
    }
}

return count;        

} }

[baddate]

class Solution {
public:
    bool check(vector<vector<int>>& matrix, int mid, int k, int n) {
        int i = n - 1;
        int j = 0;
        int num = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                num += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return num >= k;
    }

    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, mid, k, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

[C2tr]

class Solution: def kthSmallest(self, matrix: List[List[int]], k: int) -> int: lis = [] for i in range(len(matrix)): heapq.heappush(lis, (matrix[i][0], i, 0))

    for i in range(k - 1): # 每次取出最小的，总共取出k-1次即可
        num, x, y = heapq.heappop(lis)
        if y != len(matrix) - 1:
            heapq.heappush(lis, (matrix[x][y + 1], x, y + 1))

    return heapq.heappop(lis)[0]

[charlestang]

思路

堆

把每行第一个元素放近堆里。

从堆里取出一个元素扔掉，就把那个元素所在的行的下一个元素放进去，直到扔掉 K 个。

最后一个就是答案。

代码

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        heap = []

        for i in range(n):
            heapq.heappush(heap, (matrix[i][0], i, 0))

        for i in range(k - 1):
            _, j, idx = heapq.heappop(heap)
            if idx < n - 1:
                heapq.heappush(heap, (matrix[j][idx + 1], j, idx + 1))

        kth, _, _ = heap[0]

        return kth

时间复杂度 O(k logn)

空间复杂度 O(n)

[Richard-LYF]

class Solution: def kthSmallest(self, matrix: List[List[int]], k: int) -> int:

    n = len(matrix)

    def check(mid):
        i, j = n - 1, 0
        num = 0
        while i >= 0 and j < n:
            if matrix[i][j] <= mid:
                num += i + 1
                j += 1
            else:
                i -= 1
        return num >= k

    left, right = matrix[0][0], matrix[-1][-1]
    while left < right:
        mid = (left + right) // 2
        if check(mid):
            right = mid
        else:
            left = mid + 1

    return left

o nlog(r - l) o 1

[fornobugworld]

class Solution:
    import heapq
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        hp = []
        n = len(matrix)
        for i in range(n):
            for j in range(n):
                heappush(hp,-matrix[i][j])
                if len(hp)>k:
                    heappop(hp)
        return -heappop(hp)

[dahaiyidi]

Problem

[378. 有序矩阵中第 K 小的元素](https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/)

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

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

你能否用一个恒定的内存(即 O(1) 内存复杂度)来解决这个问题? 你能在 O(n) 的时间复杂度下解决这个问题吗?这个方法对于面试来说可能太超前了，但是你会发现阅读这篇文章（ this paper ）很有趣。

---

Note

• 在[240. 搜索二维矩阵 II](https://leetcode-cn.com/problems/search-a-2d-matrix-ii/)的思想上修改。
• 此题目为：二分答案的类型
• 取最小值left = matrix[0][0], 最大值right = matrix[n - 1][n - 1]，然后取中值mid
• 从右下角开始，计算matrix 中<= mid的数量num。形成一个分界线，在该线左上的均<=mid， 在该线右下的均>mid
• 基于num和k的关系，更新left与right，完成二分查找。
• 但是，应该思考怎么理解left，right的更新方式，为何while里面的条件是left<right。 有没有可能转化为标准二分形式？？？

---

Complexity

• 时间O：nlog(right -left)
• 空间O：1

---

Python

C++

class Solution {
public:
    bool check(vector<vector<int>>& matrix, int mid, int k, int n){
        // 计算matrix 中<= mid的数量
        int i = n - 1, j = 0;
        int num = 0;
        while(i >= 0 && j <= n - 1){
            if(matrix[i][j] <= mid){
                num += (i + 1);
                j++;
            }
            else{
                i--;
            }
        }
        return num >= k;
    }
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while(left < right){
            int mid = left + ((right - left) >> 1);
            if(check(matrix, mid, k, n)){
                right = mid;
            }
            else{
                left = mid + 1;
            }

        }
        return left;
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[xinhaoyi]

class Solution { public int kthSmallest(int[][] matrix, int k) { int row = matrix.length; int col = matrix[0].length; int left = matrix[0][0];

    int right = matrix[row-1][col-1];

    while(left < right){
        int mid = left + (right -left)/2;
        int count = findNotLargerThan(matrix,mid,row,col);
        if(count < k){
            left = mid+1;
        }else{
            right = mid ;
        }

    }

    return left;
}

//在一个行列都是顺序的二维数组中，找出比target小的数的个数
//从最后一行第一列开始，判断是否小于target，如果小于那么本列所有值均小于它
//然后从下一列开始比。如果大于，那么就行数向上走
public int findNotLargerThan(int [][]matrix,int target,int rows,int cols){

    int count = 0;
    int row = rows-1;
    int col = 0;

    while(row >=0  && col < cols){
        if(matrix[row][col] <= target){
            count += row+1;
            col++;
        }else{
            row--;
        }
    }

    return count;
}

}

[GaoMinghao]

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<Tuple> minHeap = new PriorityQueue<>();
        for(int i = 0; i < matrix.length; i++)
            minHeap.offer(new Tuple(i,0,matrix[i][0]));
        for(int i = 0; i < k-1; i++) {
            Tuple current = minHeap.poll();
            if(current.y < matrix.length-1)
                minHeap.offer(new Tuple(current.x, current.y+1, matrix[current.x][current.y+1]));
        }
        return minHeap.poll().val;
    }

    class Tuple implements Comparable<Tuple> {
        int x,y,val;

        public Tuple(int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }

        @Override
        public int compareTo(Tuple that) {
            return this.val - that.val;
        }
    }
}

[for123s]

class Solution {
public:
    bool findnum(vector<vector<int>> matrix,int n,int mid,int k)
    {
        int i = 0, j = n - 1;
        int ans = 0;
        while(i<n&&j>=0)
        {
            if(matrix[j][i]>mid)
            {    
                --j;
            }
            else
            {    
                ++i;
                ans += j+1;
            }
        }
        return ans >= k;
    }

    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int left = matrix[0][0], right = matrix[n-1][n-1];
        while(left<right)
        {
            int mid = left+((right-left)>>1);
            if(findnum(matrix, n, mid, k))
                right = mid;
            else
                left = mid+1;
        }
        return left;
    }
};

[ChenJingjing85]

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        def check(mid):
            row, col = n-1,0
            num = 0
            while row >= 0 and col < n:
                if matrix[row][col] <= mid:
                    num += row+1
                    col += 1
                else:
                    row -= 1
            return num >= mid
        l, r = matrix[0][0], matrix[n-1][n-1]
        while l < r:
            mid = (l+r)//2
            if check(mid):
                right = mid
            else:
                left = mid-1
        return left

[machuangmr]

代码

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<Tuple> minHeap = new PriorityQueue<>();
        for(int i = 0; i < matrix.length; i++)
            minHeap.offer(new Tuple(i,0,matrix[i][0]));
        for(int i = 0; i < k-1; i++) {
            Tuple current = minHeap.poll();
            if(current.y < matrix.length-1)
                minHeap.offer(new Tuple(current.x, current.y+1, matrix[current.x][current.y+1]));
        }
        return minHeap.poll().val;
    }

    class Tuple implements Comparable<Tuple> {
        int x,y,val;

        public Tuple(int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }

        @Override
        public int compareTo(Tuple that) {
            return this.val - that.val;
        }
    }
}

[taojin1992]

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        for (int r = 0; r < matrix.length; r++) {
            minHeap.offer(new int[]{matrix[r][0], r, 0});
        }
        int curVal = 0;
        while (!minHeap.isEmpty()) {
            int[] curEntry = minHeap.poll();
            curVal = curEntry[0];
            int curR = curEntry[1], curC = curEntry[2];
            k -= 1;
            if (k == 0) {
                break;
            }
            if (curC == matrix[0].length - 1) {
                continue;
            }
            else {
                minHeap.offer(new int[]{matrix[curR][curC + 1], curR, curC + 1});
            }
        }
        return curVal;
    }

}

[declan92]

思路 与合并k个有序链表题目相似

1. 建立长度为n的小堆顶，堆保存元素值，x坐标，y坐标；
2. 将矩阵每个元素首位offer进堆；
3. 循环k-1次poll元素，然后添加元素后一位元素进堆；
4. 返回堆首位元素的值；

java

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        Queue<int[]> heap = new PriorityQueue<>(n, new Comparator<int[]>() {
            @Override
            public int compare(int[] i1, int[] i2) {
                return i1[0] - i2[0];
            }
        });
        for (int i = 0; i < n; i++) {
            heap.offer(new int[] { matrix[i][0], i, 0 });
        }
        for (int i = 0; i < k - 1; i++) {
            int[] poll = heap.poll();
            if (poll[2] < n - 1) {
                heap.offer(new int[] { matrix[poll[1]][poll[2] + 1] , poll[1], poll[2] + 1});
            }
        }
        return heap.peek()[0];
    }

}

时间：$O（k*logn）$ 空间：$O（n）,n为矩阵长度$