本文共 1954 字，大约阅读时间需要 6 分钟。

为了找到n x n矩阵中按升序排列的第k小的元素，我们可以采用最小堆来维护候选集合。每次从堆中取出最小的元素，然后将其右边和下边的元素加入候选集合，同时记录已经访问过的位置以避免重复处理。这种方法确保了每次处理的元素都是当前最小的，从而能够正确找到第k小的元素。

方法思路

这种方法利用了优先队列按顺序处理元素的特点，确保每次处理的都是当前最小的元素，从而能够正确找到第k小的元素。

解决代码

import java.util.*;class Solution {    class Node {        int x;        int y;        int val;        Node(int x, int y, int val) {            this.x = x;            this.y = y;            this.val = val;        }    }    class NodeComparator implements Comparator
   
     {        public int compare(Node a, Node b) {            return a.val - b.val;        }    }    public int kthSmallest(int[][] matrix, int k) {        int n = matrix.length;        if (n == 0) {            return 0;        }        int[] cx = {0, 1};        int[] cy = {1, 0};        boolean[][] visited = new boolean[n][n];        PriorityQueue
    
      minHeap = new PriorityQueue<>(k, new NodeComparator());        Node start = new Node(0, 0, matrix[0][0]);        minHeap.add(start);        visited[0][0] = true;        int count = 0;        while (!minHeap.isEmpty()) {            Node node = minHeap.poll();            count++;            if (count == k) {                return matrix[node.x][node.y];            }            for (int i = 0; i < 2; i++) {                int x = node.x + cx[i];                int y = node.y + cy[i];                if (x < n && y < n && !visited[x][y]) {                    visited[x][y] = true;                    minHeap.add(new Node(x, y, matrix[x][y]));                }            }        }        return 0;    }}
    
   

代码解释

• Node类：用于存储当前处理的位置及其对应的矩阵值。
• NodeComparator：用于比较节点的大小，确保优先队列按值顺序处理。
• kthSmallest方法：主要逻辑函数，实现找到第k小的元素。
  • 初始化：将起点加入优先队列，并标记为已访问。
  • 优先队列处理：每次取出最小的元素，检查是否是第k小的。
  • 扩展相邻元素：处理当前元素的右边和下边位置，避免越界和重复访问。

这种方法通过利用优先队列和访问记录，确保高效地找到矩阵中的第k小的元素。

转载地址：http://rtvv.baihongyu.com/