Dada una array (mat[][]) , que se ordena por filas y columnas en orden creciente. Se dan dos números enteros, L y R , nuestra tarea es contar el número de elementos de la array dentro del rango [L, R].
Ejemplos:
Entrada: L = 3, R = 11, array =
{{1, 6, 9}
{2, 7, 11}
{3, 8, 12}}
Salida: 6
Explicación:
Los elementos que están en este rango [3, 11] son 3, 6, 7, 8, 9, 11.
Entrada: L = 20, R = 26, array =
{{1, 6, 19}
{2, 7, 31}
{3, 8, 42}}
Salida: 0
Explicación:
No hay ningún elemento en este rango.
Enfoque ingenuo: para resolver el problema mencionado anteriormente, el método ingenuo sería hacer un recorrido por filas a través de la array.
Para cada fila, verificamos cada elemento de esa fila y si está en el rango dado, incrementamos el conteo. Finalmente, devolvemos la cuenta.
Complejidad temporal: O(M * N), donde M es el número de filas y N es el número de columnas.
Enfoque eficiente: Para optimizar el enfoque mencionado anteriormente:
- Primero contamos los elementos que son menores que L . Vamos a considerarlo como count1 . Comenzamos a recorrer desde el último elemento de la primera columna y esto incluye los siguientes dos pasos:
- Si el elemento de iteración actual es menor que L, incrementamos count1 por la fila correspondiente + 1 ya que los elementos en esa columna sobre el elemento actual (incluido el elemento actual) deben ser menores que L. Incrementamos el índice de columna.
- Si el elemento de iteración actual es mayor o igual que L, decrementamos el índice de fila. Hacemos esto hasta que el índice de fila o columna deje de ser válido.
- A continuación contamos los elementos que son menores o iguales a R . Considerémoslo como count2 . Comenzamos a recorrer desde el último elemento de la primera columna y esto incluye dos pasos:
- Si el elemento de iteración actual es menor o igual que R, incrementamos count2 por la fila correspondiente + 1 ya que los elementos en esa columna sobre el elemento actual (incluido el elemento actual) deben ser menores o iguales a R. Incrementamos el índice de columna.
- Si el elemento de iteración actual es mayor que R, decrementamos el índice de fila. Hacemos esto hasta que el índice de fila o columna deje de ser válido.
- Finalmente, devolvemos la diferencia de la columna 2 y la columna 1, que será la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count
// all elements in a Matrix
// which lies in the given range
#include <bits/stdc++.h>
using namespace std;
#define M 3
#define N 3
// Counting elements in range [L, R]
int countElements(int mat[M][N],
int L, int R)
{
// Count elements less than L
int count1 = 0;
int row = M - 1, col = 0;
while (row >= 0 && col < N) {
// Check if the current iterating
// element is less than L
if (mat[row][col] < L) {
count1 += (row + 1);
col++;
}
else {
row--;
}
}
// counting elements less
// than or equal to R
int count2 = 0;
row = M - 1, col = 0;
while (row >= 0 && col < N) {
// Check if the current iterating
// element is less than R
if (mat[row][col] <= R) {
count2 += (row + 1);
col++;
}
else {
row--;
}
}
// return the final result
return count2 - count1;
}
// Driver code
int main()
{
int mat[M][N] = { { 1, 6, 19 },
{ 2, 7, 31 },
{ 3, 8, 42 } };
int L = 10, R = 26;
cout << countElements(mat, L, R);
return 0;
}
Java
// Java implementation to count
// all elements in a Matrix
// which lies in the given range
import java.util.*;
import java.lang.*;
class GFG{
static int N = 3;
static int M = 3;
// Counting elements in range [L, R]
static int countElements(int[][] mat,
int L, int R)
{
// Count elements less than L
int count1 = 0;
int row = M - 1, col = 0;
while (row >= 0 && col < N)
{
// Check if the current iterating
// element is less than L
if (mat[row][col] < L)
{
count1 += (row + 1);
col++;
}
else
{
row--;
}
}
// counting elements less
// than or equal to R
int count2 = 0;
row = M - 1;
col = 0;
while (row >= 0 && col < N)
{
// Check if the current iterating
// element is less than R
if (mat[row][col] <= R)
{
count2 += (row + 1);
col++;
}
else
{
row--;
}
}
// return the final result
return count2 - count1;
}
// Driver code
public static void main(String[] args)
{
int[][] mat = { { 1, 6, 19 },
{ 2, 7, 31 },
{ 3, 8, 42 } };
int L = 10, R = 26;
System.out.println(countElements(mat, L, R));
}
}
// This code is contributed by offbeat
Python3
# Python3 implementation to count # all elements in a matrix which # lies in the given range M = 3 N = 3 # Counting elements in range [L, R] def countElements(mat, L, R): # Count elements less than L count1 = 0 row = M - 1 col = 0 while row >= 0 and col < N: # Check if the current iterating # element is less than L if mat[row][col] < L: count1 += (row + 1) col += 1 else: row -= 1 # Counting elements less # than or equal to R count2 = 0 row = M - 1 col = 0 while row >= 0 and col < N: # Check if the current iterating # element is less than R if mat[row][col] <= R: count2 += (row + 1) col += 1 else: row -= 1 # Return the final result return count2 - count1 # Driver code mat = [ [ 1, 6, 19 ], [ 2, 7, 31 ], [ 3, 8, 42 ] ] L = 10 R = 26 print(countElements(mat, L, R)) # This code is contributed by divyamohan123
C#
// C# implementation to count
// all elements in a Matrix
// which lies in the given range
using System;
class GFG{
static int N = 3;
static int M = 3;
// Counting elements in range [L, R]
static int countElements(int[,] mat,
int L, int R)
{
// Count elements less than L
int count1 = 0;
int row = M - 1, col = 0;
while (row >= 0 && col < N)
{
// Check if the current iterating
// element is less than L
if (mat[row, col] < L)
{
count1 += (row + 1);
col++;
}
else
{
row--;
}
}
// counting elements less
// than or equal to R
int count2 = 0;
row = M - 1;
col = 0;
while (row >= 0 && col < N)
{
// Check if the current iterating
// element is less than R
if (mat[row, col] <= R)
{
count2 += (row + 1);
col++;
}
else
{
row--;
}
}
// return the final result
return count2 - count1;
}
// Driver code
public static void Main()
{
int[,] mat = { { 1, 6, 19 },
{ 2, 7, 31 },
{ 3, 8, 42 } };
int L = 10, R = 26;
Console.Write(countElements(mat, L, R));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript implementation to count
// all elements in a Matrix
// which lies in the given range
M = 3;
N = 3;
// Counting elements in range [L, R]
function countElements( mat, L, R)
{
// Count elements less than L
var count1 = 0;
var row = M - 1, col = 0;
while (row >= 0 && col < N) {
// Check if the current iterating
// element is less than L
if (mat[row][col] < L) {
count1 += (row + 1);
col++;
}
else {
row--;
}
}
// counting elements less
// than or equal to R
var count2 = 0;
row = M - 1, col = 0;
while (row >= 0 && col < N) {
// Check if the current iterating
// element is less than R
if (mat[row][col] <= R) {
count2 += (row + 1);
col++;
}
else {
row--;
}
}
// return the final result
return count2 - count1;
}
var mat = [ [ 1, 6, 19 ],
[ 2, 7, 31 ],
[ 3, 8, 42 ] ];
var L = 10, R = 26;
document.write( countElements(mat, L, R));
// This code is contributed by SoumikMondal
</script>
Producción:
1
Complejidad Temporal: O(M + N). M es el número de Fila y N es el número de Columna.
Complejidad del Espacio Auxiliar: O(1).
Publicación traducida automáticamente
Artículo escrito por animesh_ghosh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA