Dado un entero K y una array de tamaño N x M , donde cada elemento de la array es igual al producto de sus índices ( i * j ), la tarea es encontrar el K -ésimo elemento más pequeño en la array dada.
Ejemplos:
Entrada: N = 2, M = 3, K = 5
Salida: 4
Explicación:
La array posible para las dimensiones dadas es {{1, 2, 3}, {2, 4, 6}}
Orden ordenado de los elementos de la array: { 1, 2, 2, 3, 4, 6}
Por lo tanto, el quinto elemento más pequeño es 4 .
Entrada: N = 1, M = 10, K = 8
Salida: 8
Explicación:
La array posible para las dimensiones dadas es {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}
Por lo tanto, el octavo elemento más pequeño es 8 .
Enfoque ingenuo: el enfoque más simple es almacenar todos los elementos de la array en una array y luego encontrar el K -ésimo elemento más pequeño ordenando la array.
Complejidad de tiempo: O(N×M×log(N×M))
Espacio auxiliar: O(N×M)
Enfoque eficiente:
Para optimizar el enfoque ingenuo, la idea es utilizar el algoritmo de búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Inicialice bajo como 1 y alto como N×M, ya que el K -ésimo elemento más pequeño se encuentra entre 1 y N×M.
- Encuentre el elemento medio entre los elementos bajo y alto .
- Si el número de elementos menor que mid es mayor o igual a K, entonces actualice alto a mid-1 ya que el K- ésimo elemento más pequeño se encuentra entre bajo y medio.
- Si el número de elementos menor que mid es menor que K, actualice low to mid+1 ya que el K-ésimo elemento más pequeño se encuentra entre mid y high.
- Como los elementos en la i-ésima fila son múltiplos de i , el número de elementos menores que la mitad en la i-ésima fila se puede calcular fácilmente mediante min(mid/i, M). Entonces, la complejidad del tiempo para encontrar el número de elementos menor que la mitad se puede hacer solo en O(N) .
- Realice una búsqueda binaria hasta que low sea menor o igual que high y devuelva high + 1 como el K-ésimo elemento más pequeño de la array N×M.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define LL long long
// Function that returns true if the
// count of elements is less than mid
bool countLessThanMid(LL mid, LL N,
LL M, LL K)
{
// To store count of elements
// less than mid
LL count = 0;
// Loop through each row
for (int i = 1;
i <= min((LL)N, mid); ++i) {
// Count elements less than
// mid in the ith row
count = count + min(mid / i, M);
}
if (count >= K)
return false;
else
return true;
}
// Function that returns the Kth
// smallest element in the NxM
// Matrix after sorting in an array
LL findKthElement(LL N, LL M, LL K)
{
// Initialize low and high
LL low = 1, high = N * M;
// Perform binary search
while (low <= high) {
// Find the mid
LL mid = low + (high - low) / 2;
// Check if the count of
// elements is less than mid
if (countLessThanMid(mid, N, M, K))
low = mid + 1;
else
high = mid - 1;
}
// Return Kth smallest element
// of the matrix
return high + 1;
}
// Driver Code
int main()
{
LL N = 2, M = 3;
LL int K = 5;
cout << findKthElement(N, M, K) << endl;
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
// Function that returns true if the
// count of elements is less than mid
public static boolean countLessThanMid(int mid, int N,
int M, int K)
{
// To store count of elements
// less than mid
int count = 0;
// Loop through each row
for(int i = 1;
i <= Math.min(N, mid); ++i)
{
// Count elements less than
// mid in the ith row
count = count + Math.min(mid / i, M);
}
if (count >= K)
return false;
else
return true;
}
// Function that returns the Kth
// smallest element in the NxM
// Matrix after sorting in an array
public static int findKthElement(int N, int M, int K)
{
// Initialize low and high
int low = 1, high = N * M;
// Perform binary search
while (low <= high)
{
// Find the mid
int mid = low + (high - low) / 2;
// Check if the count of
// elements is less than mid
if (countLessThanMid(mid, N, M, K))
low = mid + 1;
else
high = mid - 1;
}
// Return Kth smallest element
// of the matrix
return high + 1;
}
// Driver code
public static void main(String[] args)
{
int N = 2, M = 3;
int K = 5;
System.out.println(findKthElement(N, M, K));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach # Function that returns true if the # count of elements is less than mid def countLessThanMid(mid, N, M, K): # To store count of elements # less than mid count = 0 # Loop through each row for i in range (1, min(N, mid) + 1): # Count elements less than # mid in the ith row count = count + min(mid // i, M) if (count >= K): return False else: return True # Function that returns the Kth # smallest element in the NxM # Matrix after sorting in an array def findKthElement(N, M, K): # Initialize low and high low = 1 high = N * M # Perform binary search while (low <= high): # Find the mid mid = low + (high - low) // 2 # Check if the count of # elements is less than mid if (countLessThanMid(mid, N, M, K)): low = mid + 1 else: high = mid - 1 # Return Kth smallest element # of the matrix return high + 1 # Driver Code if __name__ == "__main__": N = 2 M = 3 K = 5 print(findKthElement(N, M, K)) # This code is contributed by Chitranayal
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function that returns true if the
// count of elements is less than mid
public static bool countLessThanMid(int mid, int N,
int M, int K)
{
// To store count of elements
// less than mid
int count = 0;
// Loop through each row
for(int i = 1;
i <= Math.Min(N, mid); ++i)
{
// Count elements less than
// mid in the ith row
count = count + Math.Min(mid / i, M);
}
if (count >= K)
return false;
else
return true;
}
// Function that returns the Kth
// smallest element in the NxM
// Matrix after sorting in an array
public static int findKthElement(int N, int M,
int K)
{
// Initialize low and high
int low = 1, high = N * M;
// Perform binary search
while (low <= high)
{
// Find the mid
int mid = low + (high - low) / 2;
// Check if the count of
// elements is less than mid
if (countLessThanMid(mid, N, M, K))
low = mid + 1;
else
high = mid - 1;
}
// Return Kth smallest element
// of the matrix
return high + 1;
}
// Driver code
public static void Main(String[] args)
{
int N = 2, M = 3;
int K = 5;
Console.WriteLine(findKthElement(N, M, K));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
// Function that returns true if the
// count of elements is less than mid
function countLessThanMid(mid, N, M, K)
{
// To store count of elements
// less than mid
let count = 0;
// Loop through each row
for (let i = 1;
i <= Math.min(N, mid); ++i) {
// Count elements less than
// mid in the ith row
count = count + Math.min(parseInt(mid / i), M);
}
if (count >= K)
return false;
else
return true;
}
// Function that returns the Kth
// smallest element in the NxM
// Matrix after sorting in an array
function findKthElement(N, M, K)
{
// Initialize low and high
let low = 1, high = N * M;
// Perform binary search
while (low <= high) {
// Find the mid
let mid = low + parseInt((high - low) / 2);
// Check if the count of
// elements is less than mid
if (countLessThanMid(mid, N, M, K))
low = mid + 1;
else
high = mid - 1;
}
// Return Kth smallest element
// of the matrix
return high + 1;
}
// Driver Code
let N = 2, M = 3;
let K = 5;
document.write(findKthElement(N, M, K));
</script>
Producción:
4
Complejidad de tiempo: O(N×log(N×M))
Espacio auxiliar: O(1)