Dada una array nxn, donde cada fila y columna se ordena en orden no decreciente. Encuentre el k-ésimo elemento más pequeño en la array 2D dada.
Ejemplo,
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
Enfoque: Entonces, la idea es encontrar el k-ésimo elemento mínimo. Cada fila y cada columna está ordenada. Por lo tanto, se puede pensar como listas ordenadas en C y las listas deben fusionarse en una sola lista , el k-ésimo elemento de la lista debe descubrirse. Entonces, el enfoque es similar, la única diferencia es que cuando se encuentra el k-ésimo elemento, el ciclo termina.
Algoritmo:
- La idea es usar el montón mínimo. Crear un Min-Heap para almacenar los elementos
- Recorra la primera fila de principio a fin y construya un montón mínimo de elementos desde la primera fila. Una entrada de montón también almacena el número de fila y el número de columna.
- Ahora ejecute un bucle k veces para extraer el elemento mínimo del montón en cada iteración
- Obtenga el elemento mínimo (o raíz) de Min-Heap.
- Encuentre el número de fila y el número de columna del elemento mínimo.
- Reemplace la raíz con el siguiente elemento de la misma columna y mini-heapify la raíz.
- Imprime el último elemento extraído, que es el k-ésimo elemento mínimo
Implementación:
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>
Producción
7th smallest element is 30
Los códigos anteriores son aportados por RISHABH CHAUHAN.
Análisis de Complejidad:
- Complejidad del tiempo: la solución anterior implica los siguientes pasos.
- Construyendo un montón mínimo que toma tiempo O (n)
- Apile k veces, lo que lleva O (k Logn) tiempo.
- Espacio auxiliar: O(R), donde R es la longitud de una fila, ya que Min-Heap almacena una fila a la vez.
El código anterior se puede optimizar para construir un montón de tamaño k cuando k es más pequeño que n. En ese caso, el k-ésimo elemento más pequeño debe estar en las primeras k filas y k columnas.
Pronto publicaremos algoritmos más eficientes para encontrar el k-ésimo elemento más pequeño.
Este artículo ha sido compilado por Ravi Gupta. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Usando la cola de prioridad incorporada:
Mediante el uso de un comparador, podemos realizar una comparación personalizada en la cola_prioridad. Usaremos la cola_prioridad<par<int,int>> para esto.
Implementación:
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;
}
Producción
7th smallest element is 30
Complejidad de tiempo: O(n log n)
Espacio Auxiliar: O(n)
Usando la búsqueda binaria sobre el rango:
Este enfoque utiliza la búsqueda binaria para iterar sobre posibles soluciones. Lo sabemos
- respuesta >= mat[0][0]
- respuesta <= mat[N-1][N-1]
Entonces hacemos una búsqueda binaria en este rango y en cada iteración determinamos el número de elementos mayores o iguales a nuestro elemento medio actual. Los elementos mayores o iguales al elemento actual se pueden encontrar en el tiempo O (n logn) usando la búsqueda binaria.
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.
Python3
# This returns count of elements in matrix
# less than of equal to num
def getElementsGreaterThanOrEqual(num,n,mat):
ans = 0
for i in range(n):
# 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
greaterThan = 0
jump = n // 2
while(jump >= 1):
while (greaterThan + jump < n and mat[i][greaterThan + jump] <= num):
greaterThan += jump
jump //= 2
ans += greaterThan + 1
return ans
# returns kth smallest index in the matrix
def 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
l,r = mat[0][0],mat[n - 1][n - 1]
while (l <= r):
mid = l + (r - l) // 2
greaterThanOrEqualMid = getElementsGreaterThanOrEqual(mid, n, mat)
if (greaterThanOrEqualMid >= k):
r = mid - 1
else:
l = mid + 1
return l
# driver code
n = 4
mat = [[10, 20, 30, 40],[15, 25, 35, 45],[25, 29, 37, 48],[32, 33, 39, 50]]
print(f"7th smallest element is {kthSmallest(mat, 4, 7)}")
# This code is contributed by shinjanpatra
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>
Producción:
7th smallest element is 30
Análisis de Complejidad
- Complejidad de tiempo : O( y * n*logn)
Where y = log( abs(Mat[0][0] - Mat[n-1][n-1]) )
- Llamamos a la función getElementsGreaterThanOrEqual log (abs(Mat[0][0] – Mat[n-1][n-1])) veces
- La complejidad temporal de getElementsGreaterThanOrEqual es O(n logn) ya que allí hacemos búsquedas binarias n veces.
- Espacio Auxiliar : O(1)
UTILIZANDO MATRIZ:
Haremos una nueva array y copiaremos todo el contenido de la array en esta array. Después de eso, ordenaremos esa array y encontraremos el k-ésimo elemento más pequeño. Esto será tan fácil.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
int kthSmallest(int mat[4][4], int n, int k)
{
int a[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++;
}
}
sort(a, a + (n*n));
int result = a[k - 1];
return result;
}
// Driver code
int main()
{
int mat[4][4] = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 25, 29, 37, 48 },
{ 32, 33, 39, 50 } };
int res = kthSmallest(mat, 4, 7);
cout << "7th smallest element is " << res;
return 0;
}
// This code is contributed by sanjoy_62.
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;
}
}
Python3
# Python program to implement above approach
def kthSmallest(mat, n, k):
a = [0 for i in range(n*n)]
v=0
for i in range(n):
for j in range(n):
a[v] = mat[i][j]
v += 1
a.sort()
result = a[k - 1]
return result
# driver program
mat = [ [ 10, 20, 30, 40 ],
[ 15, 25, 35, 45 ],
[ 25, 29, 37, 48 ],
[ 32, 33, 39, 50 ] ]
res = kthSmallest(mat, 4, 7)
print("7th smallest element is "+ str(res))
# This code is contributed by shinjanpatra
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
Javascript
<script>
// JavaScript program to implement above approach
function kthSmallest(mat, n, k)
{
let a = new Array(n*n)
let v=0
for(let i = 0; i < n; i++)
{
for(let j = 0; j < n; j++)
{
a[v] = mat[i][j];
v++;
}
}
a.sort();
let result = a[k - 1];
return result;
}
// driver program
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,"</br>")
// This code is contributed by shinjanpatra
</script>
Producción
7th smallest element is 30
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n 2 )
Uso del enfoque de cola de prioridad
C++14
#include <bits/stdc++.h>
using namespace std;
int kthSmallest(vector<vector<int>>& matrix, int k) {
//n = size of matrix
int i,j,n=matrix.size();
//using built-in priority queue which acts as max Heap i.e. largest element will be on top
//Kth smallest element can also be seen as largest element in a priority queue of size k
//By this logic we pop elements from priority queue when its size becomes greater than k
//thus top of priority queue is kth smallest element in matrix
priority_queue<int> maxH;
if(k==1)
return matrix[0][0];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
maxH.push(matrix[i][j]);
if(maxH.size()>k)
maxH.pop();
}
}
return maxH.top();
}
int main() {
vector<vector<int>> matrix = {{1,5,9},{10,11,13},{12,13,15}};
int k = 8;
cout << "8th smallest element is " << kthSmallest(matrix,k);
return 0;
}
Java
import java.util.*;
public class Main {
public static int kthSmallest(int[][] matrix, int k)
{
// n = size of matrix
int i, j, n = matrix.length;
// using built-in priority queue which acts as max
// Heap i.e. largest element will be on top
// Kth smallest element can also be seen as largest
// element in a priority queue of size k By this
// logic we pop elements from priority queue when
// its size becomes greater than k thus top of
// priority queue is kth smallest element in matrix
PriorityQueue<Integer> maxH = new PriorityQueue<>(
Collections.reverseOrder());
if (k == 1)
return matrix[0][0];
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
maxH.add(matrix[i][j]);
if (maxH.size() > k)
maxH.poll();
}
}
return maxH.peek();
}
public static void main(String[] args)
{
int[][] matrix = { { 1, 5, 9 },
{ 10, 11, 13 },
{ 12, 13, 15 } };
int k = 8;
System.out.print("8th smallest element is "
+ kthSmallest(matrix, k));
}
}
// This code is contributed by tapeshdua420.
Python3
import heapq
def kthSmallest(matrix, k):
# n = size of matrix
n = len(matrix)
# using built-in priority queue which acts as max Heap i.e. largest element will be on top
# Kth smallest element can also be seen as largest element in a priority queue of size k
# By this logic we pop elements from priority queue when its size becomes greater than k
# thus top of priority queue is kth smallest element in matrix
maxH = []
for i in range(n):
for j in range(n):
heapq.heappush(maxH, -matrix[i][j])
if len(maxH) > k:
heapq.heappop(maxH)
return -maxH[0]
matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]]
k = 8
print("8th smallest element is", kthSmallest(matrix, k))
# This code is comtributed by Tapesh (tapeshdua420)
C#
using System;
using System.Collections.Generic;
public class GFG {
public static int kthSmallest(int[,] matrix, int k)
{
// n = size of matrix
int i, j, n = matrix.GetLength(0);
// using built-in priority queue which acts as max
// Heap i.e. largest element will be on top
// Kth smallest element can also be seen as largest
// element in a priority queue of size k By this
// logic we pop elements from priority queue when
// its size becomes greater than k thus top of
// priority queue is kth smallest element in matrix
List<int> maxH = new List<int>();
if (k == 1)
return matrix[0,0];
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
maxH.Add(matrix[i,j]);
if (maxH.Count > k){
maxH.Sort((a, b) => b.CompareTo(a));
maxH.RemoveAt(0);
}
}
}
maxH.Sort((a, b) => b.CompareTo(a));
return maxH[0];
}
public static void Main(String[] args)
{
int[,] matrix = { { 1, 5, 9 },
{ 10, 11, 13 },
{ 12, 13, 15 } };
int k = 8;
Console.Write("8th smallest element is "
+ kthSmallest(matrix, k));
}
}
// This code is contributed by shikhasingrajput
Producción
8th smallest element is 13
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA