# 按行和按列排序的 2D 數組中的第 K 個最小元素| 系列 1 > 原文： [https://www.geeksforgeeks.org/kth-smallest-element-in-a-row-wise-and-column-wise-sorted-2d-array-set-1/](https://www.geeksforgeeks.org/kth-smallest-element-in-a-row-wise-and-column-wise-sorted-2d-array-set-1/) 給定一個`n x n`矩陣，其中每一行和每一列均以非降序排列。 在給定的 2D 數組中找到第`k`個最小的元素。 **示例，** ``` Input:k = 3 and array = 10, 20, 30, 40 15, 25, 35, 45 24, 29, 37, 48 32, 33, 39, 50 Output: 20 Explanation: The 3rd smallest element is 20 Input:k = 7 and array = 10, 20, 30, 40 15, 25, 35, 45 24, 29, 37, 48 32, 33, 39, 50 Output: 30 Explanation: The 7th smallest element is 30 ``` **方法**：因此，想法是找到第`k`個最小元素。 每行和每一列進行排序。 因此，可以將其視為 [C 有序列表，并且這些列表必須合并為一個列表](https://www.geeksforgeeks.org/merge-k-sorted-linked-lists-set-2-using-min-heap/)，因此必須找出列表的第`k`個元素。 因此，方法類似，唯一的區別是找到第`k`個元素時，循環結束。 **算法**： 1. 這個想法是使用最小堆。 創建最小堆以存儲元素 2. 從頭到尾遍歷第一行，并從第一行開始構建最小的元素堆。 堆條目還存儲行號和列號。 3. 現在運行循環`k`次以在每次迭代中從堆中提取最小元素 4. 從最小堆獲取最小元素（或根）。 5. 查找最小元素的行號和列號。 6. 用同一列中的下一個元素替換根，并最小化根。 7. 打印最后提取的元素，即第`k`個最小元素 **實現**： ## C++ ```cpp // kth largest element in a 2d array sorted row-wise and column-wise #include<iostream> #include<climits> using namespace std; // A structure to store entry of heap.? The entry contains // value from 2D array, row and column numbers of the value struct HeapNode { ????int val;? // value to be stored ????int r;??? // Row number of value in 2D array ????int c;??? // Column number of value in 2D array }; // A utility function to swap two HeapNode items. void swap(HeapNode *x, HeapNode *y) { ????HeapNode z = *x; ????*x = *y; ????*y = z; } // A utility function to minheapify the node harr[i] of a heap // stored in harr[] void minHeapify(HeapNode harr[], int i, int heap_size) { ????int l = i*2 + 1; ????int r = i*2 + 2; ????int smallest = i; ????if (l < heap_size && harr[l].val < harr[i].val) ????????smallest = l; ????if (r < heap_size && harr[r].val < harr[smallest].val) ????????smallest = r; ????if (smallest != i) ????{ ????????swap(&harr[i], &harr[smallest]); ????????minHeapify(harr, smallest, heap_size); ????} } // A utility function to convert harr[] to a max heap void buildHeap(HeapNode harr[], int n) { ????int i = (n - 1)/2; ????while (i >= 0) ????{ ????????minHeapify(harr, i, n); ????????i--; ????} } // This function returns kth smallest element in a 2D array mat[][] int kthSmallest(int mat[4][4], int n, int k) { ????// k must be greater than 0 and smaller than n*n ????if (k <= 0 || k > n*n) ???????return INT_MAX; ????// Create a min heap of elements from first row of 2D array ????HeapNode harr[n]; ????for (int i = 0; i < n; i++) ????????harr[i] =? {mat[0][i], 0, i}; ????buildHeap(harr, n); ????HeapNode hr; ????for (int i = 0; i < k; i++) ????{ ???????// Get current heap root ???????hr = harr[0]; ???????// Get next value from column of root's value. If the ???????// value stored at root was last value in its column, ???????// then assign INFINITE as next value ???????int nextval = (hr.r < (n-1))? mat[hr.r + 1][hr.c]: INT_MAX; ???????// Update heap root with next value ???????harr[0] =? {nextval, (hr.r) + 1, hr.c}; ???????// Heapify root ???????minHeapify(harr, 0, n); ????} ????// Return the value at last extracted root ????return hr.val; } // driver program to test above function int main() { ??int mat[4][4] = { {10, 20, 30, 40}, ????????????????????{15, 25, 35, 45}, ????????????????????{25, 29, 37, 48}, ????????????????????{32, 33, 39, 50}, ??????????????????}; ??cout << "7th smallest element is " << kthSmallest(mat, 4, 7); ??return 0; } ```