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

偏执的太偏执、 2022-08-31 06:57 119阅读 0赞

## 题目 ##

[https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/][https_leetcode.com_problems_kth-smallest-element-in-a-sorted-matrix]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

套了下小根堆模板。

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 k
            for (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;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_kth-smallest-element-in-a-sorted-matrix]: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/a344c1957f6c4db8801d12b27e3fc156.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/ef2d85be2c6248fb996ccab76f65e3c1.png