leetcode 378. Kth Smallest Element in a Sorted Matrix | 378. 有序矩阵中第 K 小的元素（小根堆）

题目

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

题解

套了下小根堆模板。

class Solution {public int kthSmallest(int[][] matrix, int k) {int M = matrix.length;int N = matrix[0].length;int heapSize = M * N;int[] heap = new int[heapSize];int p = 0;for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {heap[p++] = matrix[i][j];}}for (int i = heapSize - 1; i >= 0; i--)heapify(heap, i, heapSize);// Top kfor (int i = 0; i < k; i++) {swap(heap, 0, --heapSize);heapify(heap, 0, heapSize);}return heap[0];}public void heapify(int[] heap, int i, int heapSize) {int L = i * 2 + 1;while (L < heapSize) {int max = L + 1 < heapSize && heap[L + 1] < heap[L] ? L + 1 : L;max = heap[max] < heap[i] ? max : i;if (max == i) break;swap(heap, max, i);i = max;L = 2 * i + 1;}}private void swap(int[] heap, int i, int j) {int tmp = heap[i];heap[i] = heap[j];heap[j] = tmp;} }

总结

以上是生活随笔为你收集整理的leetcode 378. Kth Smallest Element in a Sorted Matrix | 378. 有序矩阵中第 K 小的元素（小根堆）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。