【Day 89 】2023-05-13 - 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 。

[RestlessBreeze]

code

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

[lp1506947671]

/*
 * @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;
};

复杂度分析

• 时间复杂度：二分查找进行次数为 $$O(log(r-l))$$，每次操作时间复杂度为 O(n)，因此总的时间复杂度为 $$O(nlog(r-l))$$。
• 空间复杂度：$$O(1)$$。

[snmyj]

class Solution {
public:
    vector<int> res;
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[0].size();j++) res.push_back(matrix[i][j]);
        }
        sort(res.begin(),res.end());
        return res[k-1];
    }
};

[LIMBO42]

import queue
class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        m = len(matrix)
        grid = [0] * m
        # 优先级越小，越被先取出
        m_que = queue.PriorityQueue()
        for i, j in enumerate(grid):
            m_que.put((matrix[i][j], i))
        ans = 0
        while k != 0:
            _, i = m_que.get()
            k = k - 1
            ans = matrix[i][grid[i]]
            grid[i] = grid[i] + 1
            if grid[i] >= len(matrix[i]):
                continue
            m_que.put((matrix[i][grid[i]], i))
        return ans

[Lydia61]

378. 有序矩阵中第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;
    }
};

复杂度分析

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

[Diana21170648]

思路

小顶堆

import heapq
from typing import List
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]

**复杂度分析**
- 时间复杂度：T=O(klogn)，每次出队堆
- 空间复杂度：S=O(n)，n为每一行的长度

[kangliqi1]

/*

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

[NorthSeacoder]

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (matrix, k) {
    const heap = new MaxHeap(k);
    for (let arr of matrix) {
        for (let val of arr) {
            heap.push(val)
        }
    }
    return heap.getTop()
};
class MaxHeap {
    constructor(limit) {
        this.heap = [0];
        this.limit = limit
    }
    //大->up
    shiftUp(i) {
        while (i >> 1 > 0) {
            let parentI = i >> 1;
            const parent = this.heap[parentI];
            const cur = this.heap[i];
            if (cur > parent) {
                [this.heap[parentI], this.heap[i]] = [cur, parent];
            }
            i = parentI
        }
    }
    getMaxChild(i) {
        const len = this.heap.length - 1
        if (2 * i + 1 > len) return 2 * i;
        const left = this.heap[2 * i]
        const right = this.heap[2 * i + 1];
        if (left > right) return 2 * i;
        return 2 * i + 1
    }
    //小->下
    shiftDown(i) {
        const len = this.heap.length;
        //有子节点时
        while (2 * i < len) {
            const childI = this.getMaxChild(i);
            const child = this.heap[childI];
            const cur = this.heap[i];
            if (cur < child) {
                [this.heap[childI], this.heap[i]] = [cur, child]
            }
            i = childI;
        }
    }

    pop() {
        if (this.heap[0] === 0) return;
        const res = this.heap[1];
        this.heap[1] = this.heap[this.heap.length - 1];
        this.heap.pop();
        this.heap[0]--
        this.shiftDown(1);
        return res
    }

    getTop() {
        return this.heap[1]
    }

    push(val) {
        if (this.heap[0] < this.limit) {
            this.heap.push(val);
            this.heap[0]++
            this.shiftUp(this.heap.length - 1);
        } else {
            if (val < this.heap[1]) {
                this.heap[1] = val;
                this.shiftDown(1)
            }
        }

    }

}

[JasonQiu]

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        heap = [(matrix[0][0], 0, 0)]
        result = 0
        for _ in range(k):
            result, i, j = heapq.heappop(heap)
            if j == 0 and i < len(matrix) - 1:
                heapq.heappush(heap, (matrix[i + 1][j], i + 1, j))
            if j + 1 < len(matrix[0]):
                heapq.heappush(heap, (matrix[i][j + 1], i, j + 1))
        return result

[Fuku-L]

代码

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[0] - b[0];
            }
        });
        int n = matrix.length;
        for(int i = 0; i<n; i++){
            pq.offer(new int[]{matrix[i][0], i, 0});
        }
        for(int i = 0; i<k-1; i++){
            int[] now = pq.poll();
            if(now[2] != n - 1){
                pq.offer(new int[]{matrix[now[1]][now[2]+1], now[1], now[2]+1});
            }
        }
        return pq.poll()[0];
    }
}

复杂度分析

• 时间复杂度：O(klogn)
• 空间复杂度：O(n)

[Jetery]

class Solution {
public:
    int search(vector<vector<int>>& matrix, int target, int n) {
        int row = n - 1 ,col = 0;
        int count = 0;
        while(row >= 0 && col < n) {
            if(matrix[row][col] <= target) {
                count += row + 1;
                col ++;
            } else {
                row --;
            }
        }
        return count;
    }

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

[bookyue]

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

        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];

        while (left < right) {
            int mid = (left + right) >> 1;
            if (enough(matrix, k, mid))
                right = mid;
            else 
                left = mid + 1;
        }

        return left;
    }

    private boolean enough(int[][] matrix, int k, int x) {
        int count = 0;
        int n = matrix.length;
        int j = n - 1;

        for (int[] row : matrix) {
            while (j >= 0 && row[j] > x) j--;
            count += j + 1;
        }

        return count >= k;
    }

[joemonkeylee]

function kthSmallest(matrix: number[][], k: number): number {
    function enough(t: number): boolean {
        let i = n - 1, cnt = 0;

        for (const arr of matrix) {
            while (i >= 0 && arr[i] > t) i--;
            cnt += i + 1;
        }

        return cnt >= k;
    }

    let n = matrix.length;
    let left = matrix[0][0], right = matrix[n - 1][n - 1];

    while (left < right) {
        const mid = (left + right) >> 1;
        if (enough(mid)) right = mid;
        else left = mid + 1;
    }

    return left;
};

[tzuikuo]

思路

代码

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n=matrix[0].size();
        int left=matrix[0][0],right=matrix[n-1][n-1],med;
        while(left<right){
            if(med>0) med=(left+right)/2;
            else med=(left+right)/2-1;
            if(iflessk(med,matrix,k)) left=med+1;
            else right=med;
        }
        return left;
    }
    bool iflessk(int med,vector<vector<int>>& matrix, int k){
        int n=matrix[0].size();
        int i=n-1,j=0,cnt=0;
        while(i>=0&&j<n){
            if(matrix[i][j]<=med){
                cnt+=i+1;
                j++;
            }
            else{
                i--;
            }
        }
        if(cnt<k) return true;
        else return false;
    }
};

复杂度分析 -待定

[kofzhang]

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        data = [(matrix[i][0],i,0) for i in range(n)]  # 每一行的第一个元素放进堆中
        heapq.heapify(data)  # 堆化
        for i in range(k-1):  # 一个一个出
            v,x,y = heapq.heappop(data)
            if y<n-1:
                heapq.heappush(data,(matrix[x][y+1],x,y+1))
        return heapq.heappop(data)[0]