给定一个nxn矩阵，其中每一行和每一列都按非降序排序。在给定的2D数组中找到第k个最小元素。 实例
null
Input:k = 3 and array = 10, 20, 30, 40 15, 25, 35, 45 24, 29, 37, 48 32, 33, 39, 50 Output: 20Explanation: 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: 30Explanation: The 7th smallest element is 30
方法： 所以我们的想法是找到第k个最小元素。每一行和每一列都被排序。所以可以认为 C排序后的列表，这些列表必须合并成一个列表 ，必须找到列表中的第k个元素。所以方法是相似的，唯一的区别是当找到第k个元素时，循环结束。 算法：
- 这个想法是使用min heap。创建一个最小堆来存储元素
- 从头到尾遍历第一行，并从第一行构建一个最小的元素堆。堆条目还存储行号和列号。
- 现在运行一个循环k次，在每次迭代中从堆中提取最小元素
- 从最小堆中获取最小元素（或根）。
- 查找最小元素的行号和列号。
- 用同一列中的下一个元素替换根，并将根最小化。
- 打印最后提取的元素，这是第k个最小元素
实施：
C++
// kth largest element in a 2d array sorted row-wise and // column-wise #include <bits/stdc++.h> 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 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; if (l < heap_size&& r<heap_size && harr[l].val < harr[i].val && harr[r].val < harr[i].val){ HeapNode temp=harr[r]; harr[r]=harr[i]; harr[i]=harr[l]; harr[l]=temp; minHeapify(harr ,l,heap_size); minHeapify(harr ,r,heap_size); } if (l < heap_size && harr[l].val < harr[i].val){ HeapNode temp=harr[i]; harr[i]=harr[l]; harr[l]=temp; minHeapify(harr ,l,heap_size); } } // 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 }; 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; } // this code is contributed by Rishabh Chauhan |
JAVA
// Java program for kth largest element in a 2d // array sorted row-wise and column-wise class GFG{ // A structure to store entry of heap. // The entry contains value from 2D array, // row and column numbers of the value static class HeapNode { // Value to be stored int val; // Row number of value in 2D array int r; // Column number of value in 2D array int c; HeapNode( int val, int r, int c) { this .val = val; this .c = c; this .r = r; } } // A utility function to minheapify the node // harr[i] of a heap stored in harr[] static void minHeapify(HeapNode harr[], int i, int heap_size) { int l = 2 * i + 1 ; int r = 2 * i + 2 ; int min = i; if (l < heap_size&& r<heap_size && harr[l].val < harr[i].val && harr[r].val < harr[i].val){ HeapNode temp=harr[r]; harr[r]=harr[i]; harr[i]=harr[l]; harr[l]=temp; minHeapify(harr ,l,heap_size); minHeapify(harr ,r,heap_size); } if (l < heap_size && harr[l].val < harr[i].val){ HeapNode temp=harr[i]; harr[i]=harr[l]; harr[l]=temp; minHeapify(harr ,l,heap_size); } } // This function returns kth smallest // element in a 2D array mat[][] public static int kthSmallest( int [][] mat, int n, int k) { // k must be greater than 0 and // smaller than n*n if (k < 0 && k >= n * n) return Integer.MAX_VALUE; // Create a min heap of elements // from first row of 2D array HeapNode harr[] = new HeapNode[n]; for ( int i = 0 ; i < n; i++) { harr[i] = new HeapNode(mat[ 0 ][i], 0 , i); } HeapNode hr = new HeapNode( 0 , 0 , 0 ); for ( int i = 1 ; 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] : Integer.MAX_VALUE; // Update heap root with next value harr[ 0 ] = new HeapNode(nextVal, hr.r + 1 , hr.c); // Heapify root minHeapify(harr, 0 , n); } // Return the value at last extracted root return hr.val; } // Driver code public static void main(String args[]) { int mat[][] = { { 10 , 20 , 30 , 40 }, { 15 , 25 , 35 , 45 }, { 25 , 29 , 37 , 48 }, { 32 , 33 , 39 , 50 } }; int res = kthSmallest(mat, 4 , 7 ); System.out.print( "7th smallest element is " + res); } } // This code is contributed by Rishabh Chauhan |
Python3
# Program for kth largest element in a 2d array # sorted row-wise and column-wise from sys import maxsize # A structure to store an entry of heap. # The entry contains a value from 2D array, # row and column numbers of the value class HeapNode: def __init__( self , val, r, c): self .val = val # value to be stored self .r = r # Row number of value in 2D array self .c = c # Column number of value in 2D array # A utility function to minheapify the node harr[i] # of a heap stored in harr[] def minHeapify(harr, i, heap_size): l = i * 2 + 1 r = i * 2 + 2 if (l < heap_size and r<heap_size and harr[l].val < harr[i].val and harr[r].val < harr[i].val): temp = HeapNode( 0 , 0 , 0 ) temp = harr[r] harr[r] = harr[i] harr[i] = harr[l] harr[l] = temp minHeapify(harr ,l,heap_size) minHeapify(harr ,r,heap_size) if (l < heap_size and harr[l].val < harr[i].val): temp = HeapNode( 0 , 0 , 0 ) temp = harr[i] harr[i] = harr[l] harr[l] = temp minHeapify(harr ,l,heap_size) # This function returns kth smallest element # in a 2D array mat[][] def kthSmallest(mat, n, k): # k must be greater than 0 and smaller than n*n if k < 0 or k > n * n: return maxsize # Create a min heap of elements from # first row of 2D array harr = [ 0 ] * n for i in range (n): harr[i] = HeapNode(mat[ 0 ][i], 0 , i) hr = HeapNode( 0 , 0 , 0 ) for i in range (k): # 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 nextval = mat[hr.r + 1 ][hr.c] if (hr.r < n - 1 ) else maxsize # Update heap root with next value harr[ 0 ] = HeapNode(nextval, hr.r + 1 , hr.c) # Heapify root minHeapify(harr, 0 , n) # Return the value at last extracted root return hr.val # Driver Code if __name__ = = "__main__" : mat = [[ 10 , 20 , 30 , 40 ], [ 15 , 25 , 35 , 45 ], [ 25 , 29 , 37 , 48 ], [ 32 , 33 , 39 , 50 ]] print ( "7th smallest element is" , kthSmallest(mat, 4 , 7 )) # This code is contributed by Rishabh Chauhan |
C#
// C# program for kth largest element in a 2d // array sorted row-wise and column-wise using System; class GFG{ // A structure to store entry of heap. // The entry contains value from 2D array, // row and column numbers of the value class HeapNode { // Value to be stored public int val; // Row number of value in 2D array public int r; // Column number of value in 2D array public int c; public HeapNode( int val, int r, int c) { this .val = val; this .c = c; this .r = r; } } // A utility function to minheapify the node // harr[i] of a heap stored in harr[] static void minHeapify(HeapNode []harr, int i, int heap_size){ int l = 2 * i + 1; int r = 2 * i + 2; if (l < heap_size && r < heap_size && harr[l].val < harr[i].val && harr[r].val < harr[i].val){ HeapNode temp = new HeapNode(0, 0, 0); temp=harr[r]; harr[r]=harr[i]; harr[i]=harr[l]; harr[l]=temp; minHeapify(harr ,l,heap_size); minHeapify(harr ,r,heap_size); } if (l < heap_size && harr[l].val < harr[i].val){ HeapNode temp = new HeapNode(0, 0, 0); temp = harr[i]; harr[i]=harr[l]; harr[l]=temp; minHeapify(harr ,l,heap_size); } } // This function returns kth smallest // element in a 2D array [,]mat public static int kthSmallest( int [,] mat, int n, int k) { // k must be greater than 0 and // smaller than n*n if (k < 0 || k > n * n) { return int .MaxValue; } // Create a min heap of elements // from first row of 2D array HeapNode []harr = new HeapNode[n]; for ( int i = 0; i < n; i++) { harr[i] = new HeapNode(mat[0, i], 0, i); } HeapNode hr = new HeapNode(0, 0, 0); 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 .MaxValue; // Update heap root with next value harr[0] = new HeapNode(nextVal, hr.r + 1, hr.c); // Heapify root minHeapify(harr, 0, n); } // Return the value at last // extracted root return hr.val; } // Driver code public static void Main(String []args) { int [,]mat = { { 10, 20, 30, 40 }, { 15, 25, 35, 45 }, { 25, 29, 37, 48 }, { 32, 33, 39, 50 } }; int res = kthSmallest(mat, 4, 7); Console.Write( "7th smallest element is " + res); } } // This code is contributed by Rishabh Chauhan |
Javascript
<script> // Javascript program for kth largest element in a 2d // array sorted row-wise and column-wise // A structure to store entry of heap. // The entry contains value from 2D array, // row and column numbers of the value class HeapNode { constructor(val,r,c) { this .val = val; this .c = c; this .r = r; } } // A utility function to minheapify the node // harr[i] of a heap stored in harr[] function minHeapify(harr,i,heap_size) { let l = 2 * i + 1; let r = 2 * i + 2; let min = i; if (l < heap_size&& r<heap_size && harr[l].val < harr[i].val && harr[r].val < harr[i].val){ let temp=harr[r]; harr[r]=harr[i]; harr[i]=harr[l]; harr[l]=temp; minHeapify(harr ,l,heap_size); minHeapify(harr ,r,heap_size); } if (l < heap_size && harr[l].val < harr[i].val){ let temp=harr[i]; harr[i]=harr[l]; harr[l]=temp; minHeapify(harr ,l,heap_size); } } // This function returns kth smallest // element in a 2D array mat[][] function kthSmallest(mat,n,k) { // k must be greater than 0 and // smaller than n*n if (k < 0 && k >= n * n) return Number.MAX_VALUE; // Create a min heap of elements // from first row of 2D array let harr = new Array(n); for (let i = 0; i < n; i++) { harr[i] = new HeapNode(mat[0][i], 0, i); } let hr = new HeapNode(0, 0, 0); for (let i = 1; 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 let nextVal = hr.r < n - 1 ? mat[hr.r + 1][hr.c] : Number.MAX_VALUE; // Update heap root with next value harr[0] = new HeapNode(nextVal, hr.r + 1, hr.c); // Heapify root minHeapify(harr, 0, n); } // Return the value at last extracted root return hr.val; } // Driver code let mat=[[ 10, 20, 30, 40 ], [ 15, 25, 35, 45 ], [ 25, 29, 37, 48 ], [ 32, 33, 39, 50 ]]; let res = kthSmallest(mat, 4, 7); document.write( "7th smallest element is " + res); // This code is contributed by avanitrachhadiya2155 </script> |
输出
7th smallest element is 30
以上代码由RISHABH CHAUHAN提供。 复杂性分析：
- 时间复杂性： 上述解决方案包括以下步骤。
- 构建一个需要O（n）时间的最小堆
- Heapify k次，需要O（k Logn）时间。
- 空间复杂性： O（R），其中R是一行的长度，因为最小堆一次存储一行。
当k小于n时，可以优化上述代码以构建大小为k的堆。在这种情况下，第k个最小元素必须位于前k行和k列中。 我们很快就会发布更有效的算法来寻找第k个最小元素。 本文由拉维·古普塔编辑。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
使用内置优先级队列：
通过使用比较器，我们可以在优先级队列中进行自定义比较。我们将使用priority_queue
实施：
C++
// kth largest element in a 2d array sorted row-wise and // column-wise #include<bits/stdc++.h> using namespace std; int kthSmallest( int mat[4][4], int n, int k) { // USING LAMBDA FUNCTION // [=] IN LAMBDA FUNCTION IS FOR CAPTURING VARIABLES WHICH // ARE OUT OF SCOPE i.e. mat[r] // NOW, IT'LL COMPARE ELEMENTS OF HEAP BY ELEMENTS AT mat[first][second] // Capturing the value of mat by reference to prevent copying auto cmp = [&](pair< int , int > a,pair< int , int > b){ return mat[a.first][a.second] > mat[b.first][b.second]; }; //DECLARING priority_queue AND PUSHING FIRST ROW IN IT priority_queue<pair< int , int >,vector<pair< int , int >>, decltype (cmp)> pq(cmp); for ( int i=0; i<n; i++){ pq.push({i,0}); } //RUNNING LOOP FOR (k-1) TIMES for ( int i=1; i<k; i++){ auto p = pq.top(); pq.pop(); //AFTER POPPING, WE'LL PUSH NEXT ELEMENT OF THE ROW IN THE HEAP if (p.second+1 < n) pq.push({p.first,p.second + 1}); } // ON THE k'th ITERATION, pq.top() will be our answer. return mat[pq.top().first][pq.top().second]; } // 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; } |
输出
7th smallest element is 30
在范围内使用二进制搜索：
这种方法使用二进制搜索来迭代可能的解决方案。我们知道
- 答案>=mat[0][0]
- 答案<=mat[N-1][N-1]
所以我们在这个范围内进行二进制搜索，在每次迭代中确定大于或等于当前中间元素的元素数量。大于或等于当前元素的元素可以使用二进制搜索在O（n logn）时间内找到。
C++
#include <bits/stdc++.h> using namespace std; // This returns count of elements in matrix less than of equal to num int getElementsGreaterThanOrEqual( int num, int n, int mat[4][4]) { int ans = 0; for ( int i = 0; i < n; i++) { // if num is less than the first element then no more element in matrix // further are less than or equal to num if (mat[i][0] > num) { return ans; } // if num is greater than last element, it is greater than all elements // in that row if (mat[i][n - 1] <= num) { ans += n; continue ; } // This contain the col index of last element in matrix less than of equal // to num int greaterThan = 0; for ( int jump = n / 2; jump >= 1; jump /= 2) { while (greaterThan + jump < n && mat[i][greaterThan + jump] <= num) { greaterThan += jump; } } ans += greaterThan + 1; } return ans; } // returns kth smallest index in the matrix int kthSmallest( int mat[4][4], int n, int k) { // We know the answer lies between the first and the last element // So do a binary search on answer based on the number of elements // our current element is greater than the elements in the matrix int l = mat[0][0], r = mat[n - 1][n - 1]; while (l <= r) { int mid = l + (r - l) / 2; int greaterThanOrEqualMid = getElementsGreaterThanOrEqual(mid, n, mat); if (greaterThanOrEqualMid >= k) r = mid - 1; else l = mid + 1; } return l; } int main() { int n = 4; 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; } |
JAVA
class GFG { // This returns count of elements in // matrix less than of equal to num static int getElementsGreaterThanOrEqual( int num, int n, int mat[][]) { int ans = 0 ; for ( int i = 0 ; i < n; i++) { // if num is less than the first element // then no more element in matrix // further are less than or equal to num if (mat[i][ 0 ] > num) { return ans; } // if num is greater than last element, // it is greater than all elements // in that row if (mat[i][n - 1 ] <= num) { ans += n; continue ; } // This contain the col index of last element // in matrix less than of equal // to num int greaterThan = 0 ; for ( int jump = n / 2 ; jump >= 1 ; jump /= 2 ) { while (greaterThan + jump < n && mat[i][greaterThan + jump] <= num) { greaterThan += jump; } } ans += greaterThan + 1 ; } return ans; } // returns kth smallest index in the matrix static int kthSmallest( int mat[][], int n, int k) { // We know the answer lies between the first and the last element // So do a binary search on answer based on the number of elements // our current element is greater than the elements in the matrix int l = mat[ 0 ][ 0 ], r = mat[n - 1 ][n - 1 ]; while (l <= r) { int mid = l + (r - l) / 2 ; int greaterThanOrEqualMid = getElementsGreaterThanOrEqual(mid, n, mat); if (greaterThanOrEqualMid >= k) r = mid - 1 ; else l = mid + 1 ; } return l; } public static void main(String args[]) { int mat[][] = { { 10 , 20 , 30 , 40 }, { 15 , 25 , 35 , 45 }, { 25 , 29 , 37 , 48 }, { 32 , 33 , 39 , 50 }, }; System.out.println( "7th smallest element is " + kthSmallest(mat, 4 , 7 )); } } // This code is contributed by gfgking. |
C#
using System; public class GFG { // This returns count of elements in // matrix less than of equal to num static int getElementsGreaterThanOrEqual( int num, int n, int [,]mat) { int ans = 0; for ( int i = 0; i < n; i++) { // if num is less than the first element // then no more element in matrix // further are less than or equal to num if (mat[i,0] > num) { return ans; } // if num is greater than last element, // it is greater than all elements // in that row if (mat[i,n - 1] <= num) { ans += n; continue ; } // This contain the col index of last element // in matrix less than of equal // to num int greaterThan = 0; for ( int jump = n / 2; jump >= 1; jump /= 2) { while (greaterThan + jump < n && mat[i,greaterThan + jump] <= num) { greaterThan += jump; } } ans += greaterThan + 1; } return ans; } // returns kth smallest index in the matrix static int kthSmallest( int [,]mat, int n, int k) { // We know the answer lies between the first and the last element // So do a binary search on answer based on the number of elements // our current element is greater than the elements in the matrix int l = mat[0,0], r = mat[n - 1,n - 1]; while (l <= r) { int mid = l + (r - l) / 2; int greaterThanOrEqualMid = getElementsGreaterThanOrEqual(mid, n, mat); if (greaterThanOrEqualMid >= k) r = mid - 1; else l = mid + 1; } return l; } public static void Main(String []args) { int [,]mat = { { 10, 20, 30, 40 }, { 15, 25, 35, 45 }, { 25, 29, 37, 48 }, { 32, 33, 39, 50 }, }; Console.WriteLine( "7th smallest element is " + kthSmallest(mat, 4, 7)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // This returns count of elements in matrix // less than of equal to num function getElementsGreaterThanOrEqual(num,n,mat) { let ans = 0 for (let i = 0; i < n; i++) { // if num is less than the first element // then no more element in matrix // further are less than or equal to num if (mat[i][0] > num) { return ans; } // if num is greater than last element, // it is greater than all elements // in that row if (mat[i][n - 1] <= num) { ans += n; continue ; } // This contain the col index of last element // in matrix less than of equal // to num let greaterThan = 0; for (let jump = n / 2; jump >= 1; jump /= 2) { while (greaterThan + jump < n && mat[i][greaterThan + jump] <= num) { greaterThan += jump; } } ans += greaterThan + 1; } return ans; } // returns kth smallest index in the matrix function kthSmallest(mat,n,k) { // We know the answer lies between // the first and the last element // So do a binary search on answer // based on the number of elements // our current element is greater than // the elements in the matrix let l = mat[0][0], r = mat[n - 1][n - 1]; while (l <= r) { let mid = l + parseInt((r - l) / 2, 10); let greaterThanOrEqualMid = getElementsGreaterThanOrEqual(mid, n, mat); if (greaterThanOrEqualMid >= k) r = mid - 1; else l = mid + 1; } return l; } let n = 4; let mat = [ [10, 20, 30, 40], [15, 25, 35, 45], [25, 29, 37, 48], [32, 33, 39, 50], ]; document.write( "7th smallest element is " + kthSmallest(mat, 4, 7)); </script> |
输出：
7th smallest element is 30
复杂性分析
- 时间复杂性 : O（y*n*logn）
Where y = log( abs(Mat[0][0] - Mat[n-1][n-1]) )
- 我们多次调用getElementsCreaterAnorEqual函数log（abs（Mat[0][0]–Mat[n-1][n-1]）
- GetElementsCreaterAnorEqual的时间复杂度是O（n logn），因为在那里我们进行了n次二进制搜索。
- 空间复杂性 : O（1）
使用数组：
我们将创建一个新数组，并复制该数组中矩阵的所有内容。之后，我们将对数组进行排序，并找到第k个最小元素。这会更容易。
JAVA
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG { public static void main (String[] args) { int mat[][] = { { 10 , 20 , 30 , 40 }, { 15 , 25 , 35 , 45 }, { 25 , 29 , 37 , 48 }, { 32 , 33 , 39 , 50 } }; int res = kthSmallest(mat, 4 , 7 ); System.out.print( "7th smallest element is " + res); } static int kthSmallest( int [][]mat, int n, int k) { int [] a= new int [n*n]; int v= 0 ; for ( int i= 0 ;i<n;i++){ for ( int j= 0 ;j<n;j++){ a[v]=mat[i][j]; v++; } } Arrays.sort(a); int result=a[k- 1 ]; return result; } } |
C#
/*package whatever //do not write package name here */ using System; using System.Collections.Generic; public class GFG { public static void Main(String[] args) { int [,]mat = { { 10, 20, 30, 40 }, { 15, 25, 35, 45 }, { 25, 29, 37, 48 }, { 32, 33, 39, 50 } }; int res = kthSmallest(mat, 4, 7); Console.Write( "7th smallest element is " + res); } static int kthSmallest( int [,]mat, int n, int k) { int [] a = new int [n*n]; int v = 0; for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { a[v] = mat[i, j]; v++; } } Array.Sort(a); int result = a[k - 1]; return result; } } // This code is contributed by 29AjayKumar |
输出
7th smallest element is 30
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
