【Day 89 】2021-12-07 - 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 。

[yanglr]

思路:

这个题可以用堆排序, 也可以用二分。

下面使用堆排序实现。

方法: 使用优先队列

小顶堆。

代码:

实现语言: C++

class Solution {
public:
    int kthSmallest(vector<vector<int>>& M, int k) {
        priority_queue<int, vector<int>, greater<int>> q;
        int res;        
        const int rows = M.size();
        const int cols = M.front().size(); /* 题意: n == matrix.length == matrix[i].length >= 1 */
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                q.push(M[i][j]);
            }
        }
        while (!q.empty() && k - 1 > 0)  // 所求数的index 为k-1
        {
            q.pop();
            k--;
        }
        res = q.empty() ? -1 : q.top();
        return res;
    }
};

复杂度分析:

• 时间复杂度: O(N logN)
• 空间复杂度: O(N)

[ginnydyy]

Problem

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

Note

• binary search in range

Solution

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        if(matrix == null){
            return -1;
        }
        int n = matrix.length;
        if(n * n < k){
            return -1;
        }

        int start = matrix[0][0];
        int end = matrix[n - 1][n - 1];

        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            if(count(matrix, mid) < k){
                start = mid;
            }else{
                end = mid;
            }
        }

        if(count(matrix, start) >= k){
            return start;
        }

        return end;
    }

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

Complexity

• T: O(log(end - start) n). start is the smallest value in matrix, end is the greatest value in matrix, O(log(end - start)) is for binary search. For each find in the binary search, it costs O(n) to count the number of elements <= mid value. Overall is O(log(end - start) n).
• S: O(1).

[biancaone]

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

        n = len(matrix)
        left, right = matrix[0][0], matrix[n - 1][n - 1]

        while left + 1 < right:
            mid = (left + right) // 2

            if self.less_or_equal_than_mid(matrix, mid) < k:
                left = mid
            else:
                right = mid

        if self.less_or_equal_than_mid(matrix, left) >= k:
            return left

        return right

    def less_or_equal_than_mid(self, matrix, target):
        n = len(matrix)
        result = 0
        x, y = n - 1, 0

        while x >= 0 and y < n:
            if matrix[x][y] <= target:
                result += x + 1
                y += 1
            else:
                x -= 1

        return result

[yunomin]

思路

minheapq

代码

import heapq
class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        l = []
        element = -1
        for i in range(len(matrix)):
            heapq.heappush(l, (matrix[i][0], i, 0))
        for i in range(k):
            element, row, column = heapq.heappop(l)
            if column + 1 < len(matrix[row]): heapq.heappush(l, (matrix[row][column + 1], row, column + 1))
        return element

[zhangzz2015]

关键点

• 方法1， 可使用k路merge + heap 来找第k个元素
• 方法2， 因为有局部有序，也可使用二分查找，[0 0] 为 min [ n-1 n-1]为max，为整个搜索区间，通过二分查找，找到小于当前数值有多少个元素，和k进行比较，来排除半个区间。时间复杂度为O(log(max-min) n logn) 空间复杂度为O(1)。

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {

        // binary search. 
        int n = matrix.size(); 
        int left = matrix[0][0]; 
        int right= matrix[n-1][n-1]; 

        while(left<=right)
        {
            int middle = left + (right-left)/2; 

            int pos = lessThanValue(matrix, middle);

            if(pos >=k)
            {
                right = middle-1;                 
            }
            else
            {
                left = middle+1;  
            }                        
        }

        //  [right left]
        return left; 

    }

    int lessThanValue(vector<vector<int>>& matrix, int value)
    {

        int n = matrix.size(); 

        int ret =0;
        int dis = n; 
        for(int i=0; i< n; i++)
        {
 ///    further optimization. because next row > previou row.             
            auto it = upper_bound(matrix[i].begin(), matrix[i].begin() + dis, value); 

            dis = distance( matrix[i].begin(), it);
            ret += dis;
        }

        return ret; 

    }
};

[zhuzuojun]

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int l = INT_MIN, r = INT_MAX;
        while (l < r) {
            int mid = (long long)l + r >> 1;
            int i = matrix[0].size() - 1, cnt = 0;
            for (int j = 0; j < matrix.size(); j ++ ) {
                while (i >= 0 && matrix[j][i] > mid) i -- ;
                cnt += i + 1;
            }
            if (cnt >= k) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};

[heyqz]

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        lo, hi = matrix[0][0], matrix[-1][-1]
        while lo < hi:
            mid = (lo + hi) // 2
            if sum(bisect.bisect_right(row, mid) for row in matrix) < k:
                lo = mid + 1
            else:
                hi = mid
        return lo

[wenjialu]

method1 heap merge and sort

thought

although within each line is sorted, between lines is not sorted. why this method can make sure find the kth?? A: 维护一个最小值候选人列表，每次都从这个最小候选人列表里面弹出最小就能保证是全局最小。https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/solution/shi-yong-dui-heapde-si-lu-xiang-jie-ling-fu-python/ how： each row push 1 element to heap, heapify, push... until k times

code

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
               n = len(matrix)
        heap = [(matrix[i][0], i, 0) for i in range(n)] # init: first col of each row.
        heapq.heapify(heap)

        for i in range(k - 1):
            num, row, col = heapq.heappop(heap)# pop the samllest
            if col != n - 1:# push the ele after the smallest
                heapq.heappush(heap,(matrix[row][col + 1], row, col + 1))
        return heapq.heappop(heap)[0]

complexity

时间复杂度：O(klogn)，归并 k次，每次堆中插入和弹出的操作时间复杂度均为logn。 空间复杂度：O(n)，堆的大小始终为 n。

method2 二分

没懂。。

[JiangyanLiNEU]

class Solution {
    int pointer = 0;
    int doneRow = 0;
    int row;
    int curMax;
    int maxValue;

    public void getMaxUpdate(int[][] matrix, int[] index, int[] ordered){
        this.curMax = matrix.length-1;
        this.maxValue = matrix[matrix.length-1][matrix.length-1];
        for (this.row=0; this.row<matrix.length; this.row++){
            if (index[this.row] < matrix[0].length && matrix[this.row][index[this.row]] <= this.maxValue){
                this.maxValue = matrix[this.row][index[this.row]];
                this.curMax = this.row;
            }; 
        };
        ordered[this.pointer] = this.maxValue;
        this.pointer++;
        index[this.curMax]++;
        if (index[this.curMax] == matrix[0].length){
            this.doneRow += 1;
        };
    };
    public int kthSmallest(int[][] matrix, int k) {
        int[] index = new int[matrix.length];
        for (int i=0; i<matrix.length; i++){
            index[i] = 0;
        };
        int[] ordered = new int[matrix.length*matrix[0].length];
        while (this.doneRow !=  matrix.length){
            getMaxUpdate(matrix, index, ordered);
        };
        return ordered[k-1];
    };
}

[pan-qin]

Idea:

max heap.

Complexity:

TIme: O(NlogK). Space: O(K)

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)->(o2-o1));
        int row = matrix.length;
        int column = matrix[0].length;

        for(int i=0;i<column;i++) {
            for(int j=0;j<row;j++) {
                if(pq.size()<k) {
                    pq.offer(matrix[i][j]);
                }
                else {
                    if(matrix[i][j]<pq.peek()) {
                        pq.poll();
                        pq.offer(matrix[i][j]);
                    }
                }

            }
        }
        return pq.peek();

    }
}

[skinnyh]

Note

• Each row is a sorted list so this is similar to merge sort. Maintain a min heap of size N. Initially push all the row heads to the heap and each time pop the smallest out and push its following number to the heap. The Kth popped number is the result.

Solution

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        heap = []
        n = len(matrix)
        for i in range(n):
            # Push the head of each row to queue
            heapq.heappush(heap, (matrix[i][0], i, 0))
        res = 0
        for i in range(k):
            res, row, col = heapq.heappop(heap)
            if col < n - 1:
                heapq.heappush(heap, (matrix[row][col + 1], row, col + 1))
        return res

Time complexity: O(KlogN)

Space complexity: O(N)

[Maschinist-LZY]

C++ code

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int l = INT_MIN, r = INT_MAX;
        while (l < r) {
            int mid = (long long)l + r >> 1;
            int i = matrix[0].size() - 1, cnt = 0;
            for (int j = 0; j < matrix.size(); j ++ ) {
                while (i >= 0 && matrix[j][i] > mid) i -- ;
                cnt += i + 1;
            }
            if (cnt >= k) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};

[yingliucreates]

link:

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

代码 Javascript

const kthSmallest = function(matrix, k) {
    let lo = matrix[0][0], hi = matrix[matrix.length-1][matrix[0].length-1] + 1; // +1 because we don't want to forget the last number
    while (lo < hi) {
        let mid = lo + Math.floor((hi-lo)/2);
        let count = 0;
        for (let i = 0;i<matrix.length;i++) {
            for (let j=0;j<matrix.length;j++) {
                if (matrix[i][j] <= mid) count++;
                else break;
            }
        }
        if (count < k) lo = mid+1;
        else hi = mid;
    }
    return lo
};

[shawncvv]

思路

二分查找

代码

JavaScript Code

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;
}
/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
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(log(r-l))，每次操作时间复杂度为 O(n)，因此总的时间复杂度为 O(nlog(r-l))。
• 空间复杂度：O(1)。

[falconruo]

思路:

1. 二分查找
2. 堆排序

复杂度分析: 时间复杂度: O(n * logn), n,为矩阵matrix的行元素个数 空间复杂度: 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 count = 0;
            int row = 0;
            int col = n;

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

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

        return l;
    }
};

[shixinlovey1314]

Title:378. Kth Smallest Element in a Sorted Matrix

Question Reference LeetCode

Solution

Use a k-sized max heap, to store the k smallest elements. Since it is a max heap, the top of the heap is the kth smallest element

Code

class Solution {
public:
    void swap(int& a, int& b) {
        if (a != b) {
            a ^= b;
            b ^= a;
            a ^= b;
        }
    }
    void heap_push(vector<int>& heap, int val) {
        int n = ++heap[0];
        heap[n] = val;
        int i = n;

        while (i > 1 && heap[i] > heap[i / 2]) {
            swap(heap[i], heap[i / 2]);
            i /= 2;
        }
    }

    int getBiggerChild(vector<int>& heap, int index) {
        int l = index * 2;
        int r = index * 2 + 1;

        if (r > heap[0] || heap[l] >= heap[r])
            return l;
        return r;
    }

    void top_down(vector<int>& heap) {
        int i = 1;
        while (i <= heap[0] / 2) {
            int biggerChild = getBiggerChild(heap, i);
            if (heap[i] >= heap[biggerChild])
                break;
            swap(heap[i], heap[biggerChild]);
            i = biggerChild;
        }
    }

    int kthSmallest(vector<vector<int>>& matrix, int k) {
        std::vector<int> heap(k + 1, 0);
        heap[0] = 0;

        for (int i = 0; i < matrix.size(); i++)
            for (int j = 0; j < matrix[0].size(); j++) {
                if (heap[0] < k) {
                    heap_push(heap, matrix[i][j]);
                } else if (matrix[i][j] < heap[1]) {
                    heap[1] = matrix[i][j];
                    top_down(heap);
                }
            }

        return heap[1];
    }
};

Complexity

Time Complexity and Explanation

O(n*logk)

Space Complexity and Explanation

O(k)

[tongxw]

思路

堆排序，思路类似23题，把矩阵看成n个有序数组，找这n个有序数组的第k小的数：先把n个数组的最小数入堆，然后堆顶最小的数出堆，把它的下一个数入堆。操作k次，最后一个出堆的数字就是第k小的。

代码

class Solution {
    int m;
    int n;
    public int kthSmallest(int[][] matrix, int k) {
        m = matrix.length;
        n = matrix.length;

        // int[] { row, col, value }
        PriorityQueue<int[]> heap = new PriorityQueue<>((e1, e2) -> e1[2] - e2[2]);
        for (int i=0; i<m; i++) { // tc: O(m), sc: O(m)
            heap.offer(new int[]{i, 0, matrix[i][0]}); //tc O(logm)
        }

        int ans = 0;
        while (k > 0 && !heap.isEmpty()) { // tc O(k)
            int[] element = heap.poll();
            ans = element[2];
            int row = element[0];
            int col = element[1];
            if (col < n - 1) {
                heap.offer(new int[]{row, col + 1, matrix[row][col + 1]}); //tc O(logm)
            }
            k--;
        }

        return ans;
    }
}

• TC: O(KlogN)
• SC: O(N)

[yan0327]

堆排序

type Iheap [][]int
func(h Iheap) Len() int{return len(h)}
func(h Iheap) Less(i,j int) bool{return h[i][0]<h[j][0]}
func(h Iheap) Swap(i,j int) {h[i],h[j] = h[j],h[i]}
func(h *Iheap)Push(x interface{}){
    *h = append(*h,x.([]int))
}
func(h *Iheap)Pop() interface{}{
    x := *h
    out := x[len(x)-1]
    *h = x[:len(x)-1]
    return out
}
func kthSmallest(matrix [][]int, k int) int {
    h := Iheap{}
    m,n := len(matrix),len(matrix[0])
    if m<=0||n<=0||m*n<k{
        return 0
    }
    for i:=0;i<m;i++{
        heap.Push(&h,matrix[i])
    }
    out := 0
    for i:=0;i<k;i++{
        temp :=heap.Pop(&h).([]int)
        out = temp[0]
        temp = temp[1:]
        if len(temp) > 0{
            heap.Push(&h,temp)
        }
    }
    return out
}

二分

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 CountSum(matrix,mid,k){
            r = mid
        }else{
            l = mid+1
        }
    }
    return l
}
func CountSum(matrix [][]int,num int,k int) bool{
    count := 0
    i,j := len(matrix)-1,0
    for i>=0&&j<len(matrix){
        if matrix[i][j] <= num{
            count += i+1
            j++
        }else{
            i--
        }
    }
    return count >= k
}

[15691894985]

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

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

堆排序，有序数组，每行第一个数，为每行最小，先维护中国数字，然后不停的加下一个最小在pop指导k次

 class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        pq = [(matrix[i][0], i, 0) for i in range(n)]
        heapq.heapify(pq)
        for i in range(k - 1):
            num, x, y = heapq.heappop(pq)
            if y != n - 1:
                heapq.heappush(pq, (matrix[x][y + 1], x, y + 1))
        return heapq.heappop(pq)[0]

时间复杂度：O(klogn)

空间复杂度：O(n)

 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(klog(r-l)))

空间复杂度：O(1)

[shamworld]

const countInMatrix = (matrix, midVal) => {
  const n = matrix.length;            // 这题是方阵 n行n列
  let count = 0;
  let row = 0;                        // 第一行
  let col = n - 1;                    // 最后一列
  while (row < n && col >= 0) {
    if (midVal >= matrix[row][col]) { // 大于等于当前行的最右
      count += col + 1;               // 不大于它的数增加col + 1个
      row++;                          // 比较下一行
    } else {                          // 干不过当前行的最右元素
      col--;                          // 留在当前行，比较左边一个
    }
  }
  return count;
};

const kthSmallest = (matrix, k) => {
  const n = matrix.length;
  let low = matrix[0][0];
  let high = matrix[n - 1][n - 1];
  while (low <= high) {
    let midVal = low + ((high - low) >>> 1);   // 获取中间值
    let count = countInMatrix(matrix, midVal); // 矩阵中小于等于它的个数
    if (count < k) {
      low = midVal + 1;
    } else {
      high = midVal - 1;
    }
  }
  return low;
};

[ghost]

题目

378. Kth Smallest Element in a Sorted Matrix

代码

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

        for i in range(n):
            for j in range(n):
                if len(hq) < k:
                    heapq.heappush(hq, -matrix[i][j])
                else:
                    heapq.heappushpop(hq,-matrix[i][j])

        return -hq[0]

复杂度

Space: O(k) Time: O(n^2logk)

[jaysonss]

思路

堆排序，但要记录每个节点的row

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<Node> heap = new PriorityQueue<Node>((a,b)->a.val-b.val);
        int m = matrix.length;
        int[] idxArr = new int[m];
        Map<Integer,Integer> map = new HashMap<>();

        for(int i=0;i<m;i++){
            heap.offer(new Node(i,matrix[i][0]));
        }

        while(k>1){
            Node node = heap.poll();
            int row = node.row;
            idxArr[row]++;
            int col = idxArr[row];

            if(col<matrix[row].length){
                heap.offer(new Node(row,matrix[row][col]));
            }
            k--;
        }
        return heap.isEmpty() ? 0 : heap.peek().val;
    }

    static class Node {
        final int row;
        final int val;

        Node(int row,int val){
            this.row = row;
            this.val = val;
        }
    }
}

假设matrix 行数为m

• TC: O(k * logm)
• SC: O(m)

二分查找

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int rowLen = matrix.length;
        int colLen = matrix[0].length;
        int start = matrix[0][0], end = matrix[rowLen-1][colLen-1];

        while(start<end){
            int mid = (end -start)/2 + start;
            int lc = lessCount(matrix,mid);
            if(lc < k){
                start = mid + 1;
            }else {
                end = mid;
            }
        }
        return start;
    }

    int lessCount(int[][] matrix,int target){
        int rowLen = matrix.length;
        int colLen = matrix[0].length;
        int count = 0;

        for(int r = 0;r < rowLen; r++){
            if(matrix[r][colLen-1]<target){
                count+=colLen;
            }else {
                int end = colLen - 1;
                while(end>=0 && matrix[r][end]>target){
                    end--;
                }
                count += (end+1);
            }
        }
        return count;
    }
}

[Serena9]

代码

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

        for i in range(n):
            for j in range(n):
                if len(hq) < k:
                    heapq.heappush(hq, -matrix[i][j])
                else:
                    heapq.heappushpop(hq,-matrix[i][j])

        return -hq[0]

[wenlong201807]

代码块

/*
 * @lc app=leetcode id=378 lang=javascript
 *
 * [378] Kth Smallest Element in a Sorted Matrix
 */
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;
}
/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
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;
};

[chakochako]

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

        ret = 0
        for i in range(k - 1):
            num, x, y = heapq.heappop(pq)
            if y != n - 1:
                heapq.heappush(pq, (matrix[x][y + 1], x, y + 1))

        return heapq.heappop(pq)[0]

[chenming-cao]

解题思路

堆。多路归并问题。类似合并k个已经排好序的链表。建立小顶堆，在堆中储存元素的row和column下标数组。首先将所有n行的第一个元素的坐标放入堆中，之后每次从堆中取出最小值的坐标，然后保持row不变，column增加1。将更新的坐标放入堆中。以此方法重复k次，第k次从堆中取出的坐标即为第k小元素的坐标，根据坐标返回值即可。

代码

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        // use heap to store the row and column indices
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> matrix[a[0]][a[1]] - matrix[b[0]][b[1]]);
        // put the first element from each row to the heap
        for (int i = 0; i < n; i++) {
            heap.offer(new int[]{i, 0});
        }
        // sort to get 1st to (k - 1)th smallest elements
        for (int j = 0; j < k - 1; j++) {
            int[] cur = heap.poll();
            // check column index to see whether it is within the range, if yes, put the next element from the current row to the heap
            if (cur[1] + 1 < n) {
                heap.offer(new int[]{cur[0], cur[1] + 1});
            }
        }
        // get the index of the kth smallest element
        int[] res = heap.poll();
        return matrix[res[0]][res[1]];
    }
}

复杂度分析

• 时间复杂度：O(k*logn)
• 空间复杂度：O(n)

[muimi]

思路

二分查找

代码

class Solution {
  public int kthSmallest(int[][] matrix, int k) {
    int rows = matrix.length, cols = matrix[0].length;
    int left = matrix[0][0], right = matrix[rows - 1][cols - 1];
    while (left < right) {
      int middle = left + (right - left) / 2;
      if (check(matrix, middle, k)) {
        right = middle;
      } else {
        left = middle + 1;
      }
    }
    return left;
  }
  private boolean check(int[][] matrix, int middle, int k) {
    int nums = 0;
    int row = matrix.length - 1, col = 0;
    while (row >= 0 && col < matrix[0].length) {
      if (matrix[row][col] <= middle) {
        nums += row + 1;
        col++;
      } else {
        row--;
      }
    }
    return nums >= k;
  }
}

[RocJeMaintiendrai]

代码

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

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

复杂度分析

时间复杂度

O(nlogn)

空间复杂度

O(n)

[joeytor]

思路

使用二分查找的方法

l, r 分别为 矩阵中的最小和最大值 (左上角和右下角)

是查找满足条件的最小值的二分查找类型, 要找到最小的值 such that countnotgreaterthan(num) ≥ k, 就是最小的数字满足小于等于这个数字的个数大于等于 k

countnotgreaterthan 可以从 左下角开始遍历, 如果 数值 ≤ num, 那么代表这整个 column 都小于等于 num, 那么 count += row+1, 并且将 col 移动到下一个 column 继续搜索

否则向上搜索 row -= 1 直到数值 ≤ num 或者越界停止搜索

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

        n = len(matrix)

        def countnotgreaterthan(num):
            row, col = n-1, 0
            count = 0
            while row >= 0 and col < n:
                if matrix[row][col] <= num:
                    count += row+1
                    col += 1
                else:
                    row -= 1
            return count 

        l, r = matrix[0][0], matrix[-1][-1]
        while l <= r:
            mid = (l+r) >> 1
            count = countnotgreaterthan(mid)
            if count >= k:
                r = mid - 1
            else:
                l = mid + 1

        return l

复杂度

时间复杂度: O(nlog(r-l)) 二分查找的次数为 O(log(r-l)), 每次时间复杂度为 O(n)

空间复杂度: O(1)

[ZacheryCao]

Idea:

Heap

Code

class Solution { 
public:
    int kthSmallest(vector<vector<int>> &matrix, int k) {
        int m = matrix.size(), n = matrix[0].size(), ans; 
        priority_queue<vector<int>, vector<vector<int>>, greater<>> minHeap;
        for (int r = 0; r < min(m, k); ++r)
            minHeap.push({matrix[r][0], r, 0});

        for (int i = 1; i <= k; ++i) {
            auto top = minHeap.top(); minHeap.pop();
            int r = top[1], c = top[2];
            ans = top[0];
            if (c + 1 < n) minHeap.push({matrix[r][c + 1], r, c + 1});
        }
        return ans;
    }
};

Complexity:

Time: O(K log K) Space: O(K)

[learning-go123]

思路

• 二分

代码

• 语言支持：Go

Go Code:

func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)

    var check func(int) bool
    check = func(mid int) bool {
        count := 0
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if matrix[i][j] <= mid {
                    count++
                }
            }
        }
        return count >= k
    }

    left, right := matrix[0][0], matrix[n-1][n-1]
    for left < right {
        mid := left + (right-left)/2
        if check(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(1)$

[Tao-Mao]

Code

class Solution {

  public int kthSmallest(int[][] matrix, int k) {

    int n = matrix.length;
    int start = matrix[0][0], end = matrix[n - 1][n - 1];
    while (start < end) {

      int mid = start + (end - start) / 2;
      // first number is the smallest and the second number is the largest
      int[] smallLargePair = {matrix[0][0], matrix[n - 1][n - 1]};

      int count = this.countLessEqual(matrix, mid, smallLargePair);

      if (count == k) return smallLargePair[0];

      if (count < k) start = smallLargePair[1]; // search higher
      else end = smallLargePair[0]; // search lower
    }
    return start;
  }

  private int countLessEqual(int[][] matrix, int mid, int[] smallLargePair) {

    int count = 0;
    int n = matrix.length, row = n - 1, col = 0;

    while (row >= 0 && col < n) {

      if (matrix[row][col] > mid) {

        // as matrix[row][col] is bigger than the mid, let's keep track of the
        // smallest number greater than the mid
        smallLargePair[1] = Math.min(smallLargePair[1], matrix[row][col]);
        row--;

      } else {

        // as matrix[row][col] is less than or equal to the mid, let's keep track of the
        // biggest number less than or equal to the mid
        smallLargePair[0] = Math.max(smallLargePair[0], matrix[row][col]);
        count += row + 1;
        col++;
      }
    }

    return count;
  }
}

[ZJP1483469269]

class Solution {
    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 < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, mid, k, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public boolean check(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;
    }
}

[qixuan-code]

brute force
class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        res = []
        for i in matrix:
            res.extend(i)
        res.sort()
        return res[k-1]

[ai2095]

378. Kth Smallest Element in a Sorted Matrix

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

Topics

-HashMap -Bucket Sort

思路

-HashMap -Bucket Sort

代码 Python

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

        min_heap = []
        # Append first column
        for row in range(min(k, R)):
            min_heap.append((matrix[row][0], row, 0))

        heapq.heapify(min_heap)
        print(matrix)
        while k > 0:
            val, row, col = heapq.heappop(min_heap)
            if col < C-1:
                heapq.heappush(min_heap, (matrix[row][col+1], row, col+1))
            k -= 1

        return val

复杂度分析

let X=min(K,N) 时间复杂度： O(X+Klog⁡(X))
空间复杂度： O(X)

[Laurence-try]

class Solution:
    def countLessEqual(self, matrix, mid, smaller, larger):
        count, n = 0, len(matrix)
        row, col = n - 1, 0
        while row >= 0 and col < n:
            if matrix[row][col] > mid:
                larger = min(larger, matrix[row][col])
                row -= 1

            else:
                smaller = max(smaller, matrix[row][col])
                count += row + 1
                col += 1
        return count, smaller, larger

    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        start, end = matrix[0][0], matrix[n - 1][n - 1]
        while start < end:
            mid = start + (end - start) / 2
            smaller, larger = (matrix[0][0], matrix[n - 1][n - 1])
            count, smaller, larger = self.countLessEqual(matrix, mid, smaller, larger)
            if count == k:
                return smaller
            if count < k:
                start = larger
            else:
                end = smaller
        return start

[Moin-Jer]

思路

---

二分

代码

---

class Solution {
    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 < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, mid, k, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public boolean check(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;
    }
}

复杂度分析

---

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

[mixtureve]

class MyHeapNode {

  int row;
  int column;
  int value;

  public MyHeapNode(int v, int r, int c) {
    this.value = v;
    this.row = r;
    this.column = c;
  }

  public int getValue() {
    return this.value;
  }

  public int getRow() {
    return this.row;
  }

  public int getColumn() {
    return this.column;
  }
}

class MyHeapComparator implements Comparator<MyHeapNode> {
  public int compare(MyHeapNode x, MyHeapNode y) {
    return x.value - y.value;
  }
}

class Solution {

  public int kthSmallest(int[][] matrix, int k) {

    int N = matrix.length;

    PriorityQueue<MyHeapNode> minHeap =
        new PriorityQueue<MyHeapNode>(Math.min(N, k), new MyHeapComparator());

    // Preparing our min-heap
    for (int r = 0; r < Math.min(N, k); r++) {

      // We add triplets of information for each cell
      minHeap.offer(new MyHeapNode(matrix[r][0], r, 0));
    }

    MyHeapNode element = minHeap.peek();
    while (k-- > 0) {

      // Extract-Min
      element = minHeap.poll();
      int r = element.getRow(), c = element.getColumn();

      // If we have any new elements in the current row, add them
      if (c < N - 1) {

        minHeap.offer(new MyHeapNode(matrix[r][c + 1], r, c + 1));
      }
    }

    return element.getValue();
  }
}

[Taylucky]

哈希表

思路

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

    min_heap = []
    # Append first column
    for row in range(min(k, R)):
        min_heap.append((matrix[row][0], row, 0))

    heapq.heapify(min_heap)
    print(matrix)
    while k > 0:
        val, row, col = heapq.heappop(min_heap)
        if col < C-1:
            heapq.heappush(min_heap, (matrix[row][col+1], row, col+1))
        k -= 1

    return val

[jiahui-z]

class Solution { public int kthSmallest(int[][] matrix, int k) { int n = matrix.length; if (n == 1) return matrix[0][0];

    PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> a - b);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            minHeap.offer(matrix[i][j]);
        }
    }

    int result = 0;
    while (k > 0) {
        result = minHeap.poll();
        k--;
    }

    return result;
}

}

[HondryTravis]

思路

暴力求解

代码

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (matrix, k) {
  const ret = [];
  for (const row of matrix) {
    for (const it of row) {
      ret.push(it);
    }
  }
  ret.sort( (a, b) => a - b)
  return ret[k - 1];
};

复杂度分析

时间复杂度 O(n^2 logn)

空间复杂度 O(n^2)

[user1689]

题目

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

思路

Heap, BinarySearch

python3

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

        while(heap):
            val, x, y = heapq.heappop(heap)
            k -= 1
            if k == 0:
                return val
            if (y < n - 1):
                heapq.heappush(heap, (matrix[x][y + 1], x, y + 1))
# BinarySearch
class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        def check(mid):
            i = n - 1
            j = 0
            count = 0
            while i >= 0 and j < n:
                if (matrix[i][j] <= mid):
                    count += i + 1
                    j += 1
                else:
                    i -= 1
            return count >= k

        n = len(matrix)
        left = matrix[0][0]
        right = matrix[n - 1][n - 1]

        while (left < right):
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

复杂度分析

• time log(r-l)
• space 1

相关题目

1. 待补充

[chen445]

代码

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        hp=[]
        heapq.heappush(hp,(matrix[0][0],0,0))
        result=0
        visited=set()
        for _ in range(0,k):
            entry=heapq.heappop(hp)
            result,row,col=entry
            if row+1 < len(matrix) and (row+1,col) not in visited:
                heapq.heappush(hp,(matrix[row+1][col],row+1,col))
                visited.add((row+1,col))
            if col+1 < len(matrix) and (row,col+1) not in visited:
                heapq.heappush(hp,(matrix[row][col+1],row,col+1))
                visited.add((row,col+1))
        return result  

复杂度

Time: O(klogk)

Space: O(k)

[asterqian]

思路

binary search to count the number smaller than mid

代码

class Solution {
public:
    bool check(vector<vector<int>>& m, int k, int n, int mid) {
        int i = n - 1;
        int j = 0;
        int cnt = 0;
        while (i >= 0 && j < n) {
            if (m[i][j] <= mid) {
                cnt += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return cnt >= k;
    }
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int l = matrix[0][0];
        int r = matrix[n - 1][n - 1];
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (check(matrix, k, n, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

Time Complexity: O(nlog(r-l))

Space Complexity: O(1)

[falsity]

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

[carterrr]

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int len = matrix.length;
        int l = matrix[0][0];
        int r = matrix[len - 1][len - 1];
        while(l < r) { // 通过l r 互相逼近来得到k
            int mid = (r + l) >> 1;
            if(lessThanTCnt(matrix, mid) < k) {
                l = mid + 1; //  小于就 + 1
            } else {
                r = mid;// l != r时 有 大于等于k 此时 若r大于l仍会继续循环 >> 1  直到恰好等于k
            }
        }
        return l;
    }

    private int lessThanTCnt(int[][] matrix, int t) {
        int x = matrix.length - 1;
        int y = 0;
        int cnt = 0;
        while(x >=0 && y < matrix.length) {
            if(matrix[x][y] <= t) {
                cnt += x + 1;
                y++;
            } else {
                x --;
            }
        }
        return cnt;
    }
}

[hellowxwworld]

int kthSmallest(vector<vector<int>>& nums, int k) {
    int n = nums.size();
    vector<vector<int>> numsVect(n*n);
    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < n; ++j) 
            numsVect[i * n + j] = {i, j, nums[i][j]};

    auto cmp = [](vector<int>& p1, vector<int>& p2) {
        return p1[2] > p2[2];
    };
    priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> minPq(cmp);
    for (int i = 0; i < n; ++i) {
        minPq.push(numsVect[i * n]);
    }
    vector<int> cur;
    while (!minPq.empty()) {
        cur = minPq.top();
        minPq.pop();
        if (!--k) {
            return cur[2];
        }
        if (cur[1] < n -1)
            minPq.push(numsVect[cur[0] * n + cur[1]+1]);
        else
            minPq.push({cur[0], n, INT_MAX});
    }
    return -1;
}

[GZ712D]

代码

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

[Daniel-Zheng]

思路

二分。

代码(C++)

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

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：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]
}