Dada una array mat[][] de tamaño m * n que se ordena por filas y una array fila[] , la tarea es comprobar si alguna fila de la array es igual a la array fila[] dada .
Ejemplos:
Entrada: mat[][] = {
{1, 1, 2, 3, 1},
{2, 1, 3, 3, 2},
{2, 4, 5, 8, 3},
{4, 5, 5, 8, 3},
{8, 7, 10, 13, 6}}
fila[] = {4, 5, 5, 8, 3}
Salida: 4
4 ª fila es igual a la array dada.
Entrada: mat[][] = {
{0, 0, 1, 0},
{10, 9, 22, 23},
{40, 40, 40, 40},
{43, 44, 55, 68},
{ 81, 73, 100, 132},
{100, 75, 125, 133}}
fila[] = {10, 9, 22, 23}
Salida: 2
Enfoque ingenuo: similar a una búsqueda lineal en una array 1-D, realice la búsqueda lineal en la array y compare cada fila de la array con la array dada. Si alguna fila coincide con la array, imprima su número de fila; de lo contrario, imprima -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int m = 6, n = 4;
// Function to find a row in the
// given matrix using linear search
int linearCheck(int ar[][n], int arr[])
{
for (int i = 0; i < m; i++) {
// Assume that the current row matched
// with the given array
bool matched = true;
for (int j = 0; j < n; j++) {
// If any element of the current row doesn't
// match with the corresponding element
// of the given array
if (ar[i][j] != arr[j]) {
// Set matched to false and break;
matched = false;
break;
}
}
// If matched then return the row number
if (matched)
return i + 1;
}
// No row matched with the given array
return -1;
}
// Driver code
int main()
{
int mat[m][n] = { { 0, 0, 1, 0 },
{ 10, 9, 22, 23 },
{ 40, 40, 40, 40 },
{ 43, 44, 55, 68 },
{ 81, 73, 100, 132 },
{ 100, 75, 125, 133 } };
int row[n] = { 10, 9, 22, 23 };
cout << linearCheck(mat, row);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
class GFG
{
static int m = 6, n = 4;
// Function to find a row in the
// given matrix using linear search
static int linearCheck(int ar[][], int arr[])
{
for (int i = 0; i < m; i++)
{
// Assume that the current row matched
// with the given array
boolean matched = true;
for (int j = 0; j < n; j++)
{
// If any element of the current row doesn't
// match with the corresponding element
// of the given array
if (ar[i][j] != arr[j])
{
// Set matched to false and break;
matched = false;
break;
}
}
// If matched then return the row number
if (matched)
return i + 1;
}
// No row matched with the given array
return -1;
}
// Driver code
public static void main (String[] args)
{
int mat[][] = { { 0, 0, 1, 0 },
{ 10, 9, 22, 23 },
{ 40, 40, 40, 40 },
{ 43, 44, 55, 68 },
{ 81, 73, 100, 132 },
{ 100, 75, 125, 133 } };
int row[] = { 10, 9, 22, 23 };
System.out.println (linearCheck(mat, row));
}
}
// This code is contributed BY @Tushil..
Python3
# Python implementation of the approach m, n = 6, 4; # Function to find a row in the # given matrix using linear search def linearCheck(ar, arr): for i in range(m): # Assume that the current row matched # with the given array matched = True; for j in range(n): # If any element of the current row doesn't # match with the corresponding element # of the given array if (ar[i][j] != arr[j]): # Set matched to false and break; matched = False; break; # If matched then return the row number if (matched): return i + 1; # No row matched with the given array return -1; # Driver code if __name__ == "__main__" : mat = [ [ 0, 0, 1, 0 ], [ 10, 9, 22, 23 ], [ 40, 40, 40, 40 ], [ 43, 44, 55, 68 ], [ 81, 73, 100, 132 ], [ 100, 75, 125, 133 ] ]; row = [ 10, 9, 22, 23 ]; print(linearCheck(mat, row)); # This code is contributed by Princi Singh
C#
// C# implementation of the approach
using System;
class GFG
{
static int m = 6;
static int n = 4;
// Function to find a row in the
// given matrix using linear search
static int linearCheck(int [,]ar, int []arr)
{
for (int i = 0; i < m; i++)
{
// Assume that the current row matched
// with the given array
bool matched = true;
for (int j = 0; j < n; j++)
{
// If any element of the current row doesn't
// match with the corresponding element
// of the given array
if (ar[i,j] != arr[j])
{
// Set matched to false and break;
matched = false;
break;
}
}
// If matched then return the row number
if (matched)
return i + 1;
}
// No row matched with the given array
return -1;
}
// Driver code
static public void Main ()
{
int [,]mat = { { 0, 0, 1, 0 },
{ 10, 9, 22, 23 },
{ 40, 40, 40, 40 },
{ 43, 44, 55, 68 },
{ 81, 73, 100, 132 },
{ 100, 75, 125, 133 } };
int []row = { 10, 9, 22, 23 };
Console.Write(linearCheck(mat, row));
}
}
// This code is contributed BY ajit..
Javascript
<script>
// Javascript implementation of the approach
let m = 6, n = 4;
// Function to find a row in the
// given matrix using linear search
function linearCheck(ar, arr)
{
for (let i = 0; i < m; i++)
{
// Assume that the current row matched
// with the given array
let matched = true;
for (let j = 0; j < n; j++)
{
// If any element of the current row doesn't
// match with the corresponding element
// of the given array
if (ar[i][j] != arr[j])
{
// Set matched to false and break;
matched = false;
break;
}
}
// If matched then return the row number
if (matched)
return i + 1;
}
// No row matched with the given array
return -1;
}
let mat = [ [ 0, 0, 1, 0 ],
[ 10, 9, 22, 23 ],
[ 40, 40, 40, 40 ],
[ 43, 44, 55, 68 ],
[ 81, 73, 100, 132 ],
[ 100, 75, 125, 133 ] ];
let row = [ 10, 9, 22, 23 ];
document.write(linearCheck(mat, row));
</script>
Producción:
2
Complejidad de tiempo: O(m * n)
Enfoque eficiente: dado que la array se ordena por filas, podemos usar una búsqueda binaria similar a lo que hacemos en una array 1-D. Es necesario que la array se ordene por filas. A continuación se muestran los pasos para encontrar una fila en la array mediante la búsqueda binaria,
- Compare arr[] con la fila del medio.
- Si arr[] coincide completamente con la fila del medio, devolvemos el índice medio.
- De lo contrario, si arr[] es mayor que la mitad de la fila (existe al menos una j, 0<=j<n tal que ar[mid][j]<arr[j]), entonces arr[] solo puede estar en subarreglo de la mitad derecha después de la fila central. Así que comprobamos en la mitad inferior.
- De lo contrario (arr[] es más pequeño), verificamos en la mitad superior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int m = 6, n = 4;
// Function that compares both the arrays
// and returns -1, 0 and 1 accordingly
int compareRow(int a1[], int a2[])
{
for (int i = 0; i < n; i++) {
// Return 1 if mid row is less than arr[]
if (a1[i] < a2[i])
return 1;
// Return 1 if mid row is greater than arr[]
else if (a1[i] > a2[i])
return -1;
}
// Both the arrays are equal
return 0;
}
// Function to find a row in the
// given matrix using binary search
int binaryCheck(int ar[][n], int arr[])
{
int l = 0, r = m - 1;
while (l <= r) {
int mid = (l + r) / 2;
int temp = compareRow(ar[mid], arr);
// If current row is equal to the given
// array then return the row number
if (temp == 0)
return mid + 1;
// If arr[] is greater, ignore left half
else if (temp == 1)
l = mid + 1;
// If arr[] is smaller, ignore right half
else
r = mid - 1;
}
// No valid row found
return -1;
}
// Driver code
int main()
{
int mat[m][n] = { { 0, 0, 1, 0 },
{ 10, 9, 22, 23 },
{ 40, 40, 40, 40 },
{ 43, 44, 55, 68 },
{ 81, 73, 100, 132 },
{ 100, 75, 125, 133 } };
int row[n] = { 10, 9, 22, 23 };
cout << binaryCheck(mat, row);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int m = 6, n = 4;
// Function that compares both the arrays
// and returns -1, 0 and 1 accordingly
static int compareRow(int a1[], int a2[])
{
for (int i = 0; i < n; i++)
{
// Return 1 if mid row is less than arr[]
if (a1[i] < a2[i])
return 1;
// Return 1 if mid row is greater than arr[]
else if (a1[i] > a2[i])
return -1;
}
// Both the arrays are equal
return 0;
}
// Function to find a row in the
// given matrix using binary search
static int binaryCheck(int ar[][], int arr[])
{
int l = 0, r = m - 1;
while (l <= r)
{
int mid = (l + r) / 2;
int temp = compareRow(ar[mid], arr);
// If current row is equal to the given
// array then return the row number
if (temp == 0)
return mid + 1;
// If arr[] is greater, ignore left half
else if (temp == 1)
l = mid + 1;
// If arr[] is smaller, ignore right half
else
r = mid - 1;
}
// No valid row found
return -1;
}
// Driver code
public static void main(String[] args)
{
int mat[][] = { { 0, 0, 1, 0 },
{ 10, 9, 22, 23 },
{ 40, 40, 40, 40 },
{ 43, 44, 55, 68 },
{ 81, 73, 100, 132 },
{ 100, 75, 125, 133 } };
int row[] = { 10, 9, 22, 23 };
System.out.println(binaryCheck(mat, row));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach m = 6; n = 4; # Function that compares both the arrays # and returns -1, 0 and 1 accordingly def compareRow(a1, a2) : for i in range(n) : # Return 1 if mid row is less than arr[] if (a1[i] < a2[i]) : return 1; # Return 1 if mid row is greater than arr[] elif (a1[i] > a2[i]) : return -1; # Both the arrays are equal return 0; # Function to find a row in the # given matrix using binary search def binaryCheck(ar, arr) : l = 0; r = m - 1; while (l <= r) : mid = (l + r) // 2; temp = compareRow(ar[mid], arr); # If current row is equal to the given # array then return the row number if (temp == 0) : return mid + 1; # If arr[] is greater, ignore left half elif (temp == 1) : l = mid + 1; # If arr[] is smaller, ignore right half else : r = mid - 1; # No valid row found return -1; # Driver code if __name__ == "__main__" : mat = [ [ 0, 0, 1, 0 ], [ 10, 9, 22, 23 ], [ 40, 40, 40, 40 ], [ 43, 44, 55, 68 ], [ 81, 73, 100, 132 ], [ 100, 75, 125, 133 ] ]; row = [ 10, 9, 22, 23 ]; print(binaryCheck(mat, row)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int m = 6, n = 4;
// Function that compares both the arrays
// and returns -1, 0 and 1 accordingly
static int compareRow(int []a1, int []a2)
{
for (int i = 0; i < n; i++)
{
// Return 1 if mid row is less than arr[]
if (a1[i] < a2[i])
return 1;
// Return 1 if mid row is greater than arr[]
else if (a1[i] > a2[i])
return -1;
}
// Both the arrays are equal
return 0;
}
// Function to find a row in the
// given matrix using binary search
static int binaryCheck(int [,]ar, int []arr)
{
int l = 0, r = m - 1;
while (l <= r)
{
int mid = (l + r) / 2;
int temp = compareRow(GetRow(ar, mid), arr);
// If current row is equal to the given
// array then return the row number
if (temp == 0)
return mid + 1;
// If arr[] is greater, ignore left half
else if (temp == 1)
l = mid + 1;
// If arr[] is smaller, ignore right half
else
r = mid - 1;
}
// No valid row found
return -1;
}
public static int[] GetRow(int[,] matrix, int row)
{
var rowLength = matrix.GetLength(1);
var rowVector = new int[rowLength];
for (var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row, i];
return rowVector;
}
// Driver code
public static void Main(String[] args)
{
int [,]mat = {{ 0, 0, 1, 0 },
{ 10, 9, 22, 23 },
{ 40, 40, 40, 40 },
{ 43, 44, 55, 68 },
{ 81, 73, 100, 132 },
{ 100, 75, 125, 133 }};
int []row = { 10, 9, 22, 23 };
Console.WriteLine(binaryCheck(mat, row));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
var m = 6, n = 4;
// Function that compares both the arrays
// and returns -1, 0 and 1 accordingly
function compareRow(a1, a2)
{
for (var i = 0; i < n; i++) {
// Return 1 if mid row is less than arr[]
if (a1[i] < a2[i])
return 1;
// Return 1 if mid row is greater than arr[]
else if (a1[i] > a2[i])
return -1;
}
// Both the arrays are equal
return 0;
}
// Function to find a row in the
// given matrix using binary search
function binaryCheck(ar, arr)
{
var l = 0, r = m - 1;
while (l <= r) {
var mid = parseInt((l + r) / 2);
var temp = compareRow(ar[mid], arr);
// If current row is equal to the given
// array then return the row number
if (temp == 0)
return mid + 1;
// If arr[] is greater, ignore left half
else if (temp == 1)
l = mid + 1;
// If arr[] is smaller, ignore right half
else
r = mid - 1;
}
// No valid row found
return -1;
}
// Driver code
var mat = [ [ 0, 0, 1, 0 ],
[ 10, 9, 22, 23 ],
[ 40, 40, 40, 40 ],
[ 43, 44, 55, 68 ],
[ 81, 73, 100, 132 ],
[ 100, 75, 125, 133 ] ];
var row = [10, 9, 22, 23];
document.write( binaryCheck(mat, row));
</script>
Producción:
2
Complejidad del tiempo: O(n * log(m))