Dada una array estrictamente ordenada xn y un valor x . El problema es contar los elementos menores o iguales a x en la array dada. Aquí, array estrictamente ordenada significa que la array se ordena de tal manera que todos los elementos de una fila se ordenan en orden creciente y para la fila ‘i’, donde 1 <= i <= n-1, el primer elemento de la fila ‘i’ es mayor o igual que el último elemento de la fila ‘i-1’. Ejemplos:
Input : mat[][] = { {1, 4, 5},
{6, 10, 11},
{12, 15, 20} }
x = 9
Output : 4
The elements smaller than '9' are:
1, 4, 5 and 6.
Input : mat[][] = { {1, 4, 7, 8},
{10, 10, 12, 14},
{15, 26, 30, 31},
{31, 42, 46, 50} }
x = 31
Output : 13
Enfoque ingenuo: Atraviese la array utilizando dos bucles anidados y cuente los elementos menores o iguales que x . La complejidad del tiempo es de O (n ^ 2). Enfoque eficiente: como la array está estrictamente ordenada, utilice el concepto de técnica de búsqueda binaria. Primero aplique la técnica de búsqueda binaria en los elementos de la primera columna para encontrar el número de índice de fila del elemento más grande menor que igual a ‘x’. Para duplicados, obtenga el número de índice de la última fila de ocurrencia del elemento requerido ‘x’. Que sea fila_no. . Si no existe tal fila, devuelva 0. De lo contrario, aplique el concepto de técnica de búsqueda binaria para encontrar el número de índice de columna del elemento más grande menor o igual a ‘x’ en la fila representada por row_no . Déjalo col_no. Finalmente regresa ((row_no) * n) + (col_no + 1). El concepto de técnica de búsqueda binaria puede entenderse mediante la función binary_search de esta publicación.
C++
// C++ implementation to count elements smaller than
// or equal to x in a sorted matrix
#include <bits/stdc++.h>
using namespace std;
#define SIZE 100
// function returns the row index no of largest element
// smaller than equal to 'x' in first column of mat[][].
// For duplicates it returns the last row index no of
// occurrence of required element 'x'. If no such element
// exits then it returns -1.
int binarySearchOnRow(int mat[SIZE][SIZE],
int l, int h, int x)
{
while (l <= h) {
int mid = (l + h) / 2;
// if 'x' is greater than or equal to mat[mid][0],
// then search in mat[mid+1...h][0]
if (mat[mid][0] <= x)
l = mid + 1;
// else search in mat[l...mid-1][0]
else
h = mid - 1;
}
// required row index number
return h;
}
// function returns the column index no of largest element
// smaller than equal to 'x' in mat[row][].
// For duplicates it returns the last column index no of
// occurrence of required element 'x'.
int binarySearchOnCol(int mat[SIZE][SIZE],
int l, int h, int x, int row)
{
while (l <= h) {
int mid = (l + h) / 2;
// if 'x' is greater than or equal to mat[row][mid],
// then search in mat[row][mid+1...h]
if (mat[row][mid] <= x)
l = mid + 1;
// else search in mat[row][l...mid-1]
else
h = mid - 1;
}
// required column index number
return h;
}
// function to count elements smaller than
// or equal to x in a sorted matrix
int countSmallElements(int mat[SIZE][SIZE],
int n, int x)
{
// to get the row index number of the largest element
// smaller than equal to 'x' in mat[][]
int row_no = binarySearchOnRow(mat, 0, n - 1, x);
// if no such row exists
if (row_no == -1)
return 0;
// to get the column index number of the largest element
// smaller than equal to 'x' in mat[row_no][]
int col_no = binarySearchOnCol(mat, 0, n - 1, x, row_no);
// required count of elements
return ((row_no)*n) + (col_no + 1);
}
// Driver program to test above
int main()
{
int mat[SIZE][SIZE] = { { 1, 4, 7, 8 },
{ 10, 10, 12, 14 },
{ 15, 26, 30, 31 },
{ 31, 42, 46, 50 } };
int n = 4;
int x = 31;
cout << "Count = "
<< countSmallElements(mat, n, x);
return 0;
}
Java
//Java implementation to count elements
// smaller than or equal to x in a sorted matrix
import java.io.*;
class GFG {
static int SIZE=100;
// function returns the row index
//no of largest element smaller than
// equal to 'x' in first column of
//mat[][].For duplicates it returns
//the last row index no of
// occurrence of required element
// 'x'. If no such element
// exits then it returns -1.
static int binarySearchOnRow(int[][] mat,
int l, int h, int x)
{
while (l <= h) {
int mid = (l + h) / 2;
// if 'x' is greater than or
// equal to mat[mid][0],then
// search in mat[mid+1...h][0]
if (mat[mid][0] <= x)
l = mid + 1;
// else search in mat[l...mid-1][0]
else
h = mid - 1;
}
// required row index number
return h;
}
// function returns the column index
// no of largest element
// smaller than equal to 'x' in
// mat[row][].For duplicates it returns
// the last column index no of
// occurrence of required element 'x'.
static int binarySearchOnCol(int[][] mat,
int l, int h, int x, int row)
{
while (l <= h) {
int mid = (l + h) / 2;
// if 'x' is greater than or
// equal to mat[row][mid], then
// search in mat[row][mid+1...h]
if (mat[row][mid] <= x)
l = mid + 1;
// else search in mat[row][l...mid-1]
else
h = mid - 1;
}
// required column index number
return h;
}
// function to count elements smaller than
// or equal to x in a sorted matrix
static int countSmallElements(int[][] mat,
int n, int x)
{
// to get the row index number of the largest
// element smaller than equal to 'x' in mat[][]
int row_no = binarySearchOnRow(mat,
0, n - 1, x);
// if no such row exists
if (row_no == -1)
return 0;
// to get the column index number of
// the largest element smaller than
// equal to 'x' in mat[row_no][]
int col_no = binarySearchOnCol(mat,
0, n - 1, x, row_no);
// required count of elements
return ((row_no) * n) + (col_no + 1);
}
// Driver code
public static void main (String[] args) {
int mat[][] = { { 1, 4, 7, 8 },
{ 10, 10, 12, 14 },
{ 15, 26, 30, 31 },
{ 31, 42, 46, 50 } };
int n = 4;
int x = 31;
System.out.println("Count = "
+ countSmallElements(mat, n, x));
}
}
// This code is contributed by Gitanjali.
C#
//Java implementation to count elements
// smaller than or equal to x in a sorted matrix
using System;
class GFG {
//static int SIZE=100;
// function returns the row index
//no of largest element smaller than
// equal to 'x' in first column of
//mat[][].For duplicates it returns
//the last row index no of
// occurrence of required element
// 'x'. If no such element
// exits then it returns -1.
static int binarySearchOnRow(int [,] mat, int l,
int h, int x)
{
while (l <= h) {
int mid = (l + h) / 2;
// if 'x' is greater than or
// equal to mat[mid][0],then
// search in mat[mid+1...h][0]
if (mat[mid,0] <= x)
l = mid + 1;
// else search in mat[l...mid-1][0]
else
h = mid - 1;
}
// required row index number
return h;
}
// function returns the column index
// no of largest element
// smaller than equal to 'x' in
// mat[row][].For duplicates it returns
// the last column index no of
// occurrence of required element 'x'.
static int binarySearchOnCol(int [,]mat, int l,
int h, int x, int row)
{
while (l <= h) {
int mid = (l + h) / 2;
// if 'x' is greater than or
// equal to mat[row][mid], then
// search in mat[row][mid+1...h]
if (mat[row,mid] <= x)
l = mid + 1;
// else search in mat[row][l...mid-1]
else
h = mid - 1;
}
// required column index number
return h;
}
// function to count elements smaller than
// or equal to x in a sorted matrix
static int countSmallElements(int[,] mat,
int n, int x)
{
// to get the row index number of the largest
// element smaller than equal to 'x' in mat[][]
int row_no = binarySearchOnRow(mat,
0, n - 1, x);
// if no such row exists
if (row_no == -1)
return 0;
// to get the column index number of
// the largest element smaller than
// equal to 'x' in mat[row_no][]
int col_no = binarySearchOnCol(mat,
0, n - 1, x, row_no);
// required count of elements
return ((row_no) * n) + (col_no + 1);
}
// Driver code
public static void Main () {
int [,]mat = { { 1, 4, 7, 8 },
{ 10, 10, 12, 14 },
{ 15, 26, 30, 31 },
{ 31, 42, 46, 50 } };
int n = 4;
int x = 31;
Console.WriteLine("Count = "
+ countSmallElements(mat, n, x));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP implementation to count
// elements smaller than or
// equal to x in a sorted matrix
// function returns the row index
// no of largest element smaller
// than equal to 'x' in first
// column of mat[][]. For duplicates
// it returns the last row index no.
// of occurrence of required element
// 'x'. If no such element exits then
// it returns -1.
function binarySearchOnRow($mat, $l,
$h, $x)
{
while ($l <= $h) {
$mid = floor(($l + $h) / 2);
// if 'x' is greater than
// or equal to mat[mid][0],
// then search in
// mat[mid+1...h][0]
if ($mat[$mid][0] <= $x)
$l = $mid + 1;
// else search in
// mat[l...mid-1][0]
else
$h = $mid - 1;
}
// required row index number
return $h;
}
// function returns the column
// index no of largest element
// smaller than equal to 'x'
// in mat[row][]. For duplicates
// it returns the last column
// index no of occurrence of
// required element 'x'.
function binarySearchOnCol($mat, $l,
$h, $x, $row)
{
while ($l <= $h) {
$mid = floor(($l + $h) / 2);
// if 'x' is greater than or
// equal to mat[row][mid],
// then search in
// mat[row][mid+1...h]
if ($mat[$row][$mid] <= $x)
$l = $mid + 1;
// else search in
// mat[row][l...mid-1]
else
$h = $mid - 1;
}
// required column
// index number
return $h;
}
// function to count elements
// smaller than or equal to x
// in a sorted matrix
function countSmallElements($mat,
$n, $x)
{
// to get the row index number
// of the largest element
// smaller than equal to 'x'
// in mat[][]
$row_no = binarySearchOnRow($mat, 0,
$n - 1, $x);
// if no such row exists
if ($row_no == -1)
return 0;
// to get the column index
// number of the largest element
// smaller than equal to 'x'
// in mat[row_no][]
$col_no = binarySearchOnCol($mat, 0,
$n - 1, $x, $row_no);
// required count of elements
return floor(($row_no) * $n) +
($col_no + 1);
}
// Driver Code
$mat = array(array(1, 4, 7, 8),
array(10, 10, 12, 14),
array(15, 26, 30, 31),
array(31, 42, 46, 50));
$n = 4;
$x = 31;
echo "Count = ", countSmallElements ($mat, $n, $x);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// JavaScript implementation to
// count elements smaller than
// or equal to x in a sorted matrix
const SIZE = 100
// function returns the row index
// no of largest element
// smaller than equal to 'x' in
// first column of mat[][].
// For duplicates it returns the
// last row index no of
// occurrence of required element
// 'x'. If no such element
// exits then it returns -1.
function binarySearchOnRow(mat, l, h, x){
while(l <= h){
let mid = Math.floor((l + h) / 2)
// if 'x' is greater than or
// equal to mat[mid][0],
// then search in mat[mid+1...h][0]
if(mat[mid][0] <= x)
l = mid + 1
// else search in mat[l...mid-1][0]
else
h = mid - 1
}
// required row index number
return h
}
// function returns the column
// index no of largest element
// smaller than equal to 'x'
// in mat[row][].
// For duplicates it returns the
// last column index no of
// occurrence of required element 'x'.
function binarySearchOnCol(mat, l, h, x, row){
while(l <= h){
let mid = Math.floor((l + h) / 2)
// if 'x' is greater than or
// equal to mat[row][mid],
// then search in mat[row][mid+1...h]
if(mat[row][mid] <= x)
l = mid + 1
// else search in mat[row][l...mid-1]
else
h = mid - 1
}
// required column index number
return h
}
// function to count elements smaller than
// or equal to x in a sorted matrix
function countSmallElements(mat, n, x){
// to get the row index number
// of the largest element
// smaller than equal to 'x' in mat[][]
let row_no = binarySearchOnRow(mat, 0, n - 1, x)
// if no such row exists
if(row_no == -1)
return 0
// to get the column index number
// of the largest element
// smaller than equal to 'x' in mat[row_no][]
let col_no = binarySearchOnCol(mat, 0,
n - 1, x, row_no)
// required count of elements
return ((row_no)*n) + (col_no + 1)
}
// Driver program to test above
let mat = [ [ 1, 4, 7, 8 ],
[ 10, 10, 12, 14 ],
[ 15, 26, 30, 31 ],
[ 31, 42, 46, 50 ] ]
let n = 4
let x = 31
document.write("Count = " + countSmallElements(mat, n, x))
// This code is contributed by shinjanpatra
</script>
Producción:
Count = 13
Complejidad temporal: O(Log 2 n).
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA