Dada una array de rango limitado que contiene números positivos y no positivos, es decir, los elementos están en el rango de -MAX a +MAX. Nuestra tarea es buscar si algún número está presente en el arreglo o no en el tiempo O(1).
Dado que el rango es limitado, podemos usar el mapeo de índices (o hashing trivial). Usamos valores como índice en una gran array. Por lo tanto podemos buscar e insertar elementos en tiempo O(1).
¿Cómo manejar los números negativos?
La idea es utilizar una array 2D de hash de tamaño [MAX+1][2]
Algoritmo:
Asigne todos los valores de la array hash como 0.
Recorre la array dada:
- Si el elemento ele no es negativo asignar
- hash[ ele ][0] como 1.
- De lo contrario, tome el valor absoluto de ele y
- asigne hash[ ele ][1] como 1.
Para buscar cualquier elemento x en la array.
- Si X no es negativo, compruebe si hash[X][0] es 1 o no. Si hash[X][0] es uno, entonces el número está presente, de lo contrario no está presente.
- Si X es negativo, tome el valor absoluto de X y luego verifique si hash[X][1] es 1 o no. Si hash[X][1] es uno, entonces el número está presente
A continuación se muestra la implementación de la idea anterior.
C++
// CPP program to implement direct index mapping
// with negative values allowed.
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
// Since array is global, it is initialized as 0.
bool has[MAX + 1][2];
// searching if X is Present in the given array
// or not.
bool search(int X)
{
if (X >= 0) {
if (has[X][0] == 1)
return true;
else
return false;
}
// if X is negative take the absolute
// value of X.
X = abs(X);
if (has[X][1] == 1)
return true;
return false;
}
void insert(int a[], int n)
{
for (int i = 0; i < n; i++) {
if (a[i] >= 0)
has[a[i]][0] = 1;
else
has[abs(a[i])][1] = 1;
}
}
// Driver code
int main()
{
int a[] = { -1, 9, -5, -8, -5, -2 };
int n = sizeof(a)/sizeof(a[0]);
insert(a, n);
int X = -5;
if (search(X) == true)
cout << "Present";
else
cout << "Not Present";
return 0;
}
Java
// Java program to implement direct index
// mapping with negative values allowed.
class GFG
{
final static int MAX = 1000;
// Since array is global, it
// is initialized as 0.
static boolean[][] has = new boolean[MAX + 1][2];
// searching if X is Present in
// the given array or not.
static boolean search(int X)
{
if (X >= 0)
{
if (has[X][0] == true)
{
return true;
}
else
{
return false;
}
}
// if X is negative take the
// absolute value of X.
X = Math.abs(X);
if (has[X][1] == true)
{
return true;
}
return false;
}
static void insert(int a[], int n)
{
for (int i = 0; i < n; i++)
{
if (a[i] >= 0)
{
has[a[i]][0] = true;
}
else
{
int abs_i = Math.Abs(a[i]);
has[abs_i][1] = true;
}
}
}
// Driver code
public static void main(String args[])
{
int a[] = {-1, 9, -5, -8, -5, -2};
int n = a.length;
insert(a, n);
int X = -5;
if (search(X) == true)
{
System.out.println("Present");
}
else
{
System.out.println("Not Present");
}
}
}
// This code is contributed
// by 29AjayKumar
Python3
# Python3 program to implement direct index
# mapping with negative values allowed.
# Searching if X is Present in the
# given array or not.
def search(X):
if X >= 0:
return has[X][0] == 1
# if X is negative take the absolute
# value of X.
X = abs(X)
return has[X][1] == 1
def insert(a, n):
for i in range(0, n):
if a[i] >= 0:
has[a[i]][0] = 1
else:
has[abs(a[i])][1] = 1
# Driver code
if __name__ == "__main__":
a = [-1, 9, -5, -8, -5, -2]
n = len(a)
MAX = 1000
# Since array is global, it is
# initialized as 0.
has = [[0 for i in range(2)]
for j in range(MAX + 1)]
insert(a, n)
X = -5
if search(X) == True:
print("Present")
else:
print("Not Present")
# This code is contributed by Rituraj Jain
C#
// C# program to implement direct index
// mapping with negative values allowed.
using System;
class GFG
{
static int MAX = 1000;
// Since array is global, it
// is initialized as 0.
static bool[,] has = new bool[MAX + 1, 2];
// searching if X is Present in
// the given array or not.
static bool search(int X)
{
if (X >= 0)
{
if (has[X, 0] == true)
{
return true;
}
else
{
return false;
}
}
// if X is negative take the
// absolute value of X.
X = Math.Abs(X);
if (has[X, 1] == true)
{
return true;
}
return false;
}
static void insert(int[] a, int n)
{
for (int i = 0; i < n; i++)
{
if (a[i] >= 0)
{
has[a[i], 0] = true;
}
else
{
int abs_i = Math.Abs(a[i]);
has[abs_i, 1] = true;
}
}
}
// Driver code
public static void Main()
{
int[] a = {-1, 9, -5, -8, -5, -2};
int n = a.Length;
insert(a, n);
int X = -5;
if (search(X) == true)
{
Console.WriteLine("Present");
}
else
{
Console.WriteLine("Not Present");
}
}
}
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// JavaScript program to implement direct index
// mapping with negative values allowed.
let MAX = 1000;
// Since array is global, it
// is initialized as 0.
let has = new Array(MAX+1);
for(let i=0;i<MAX+1;i++)
{
has[i]=new Array(2);
for(let j=0;j<2;j++)
has[i][j]=0;
}
// searching if X is Present in
// the given array or not.
function search(X)
{
if (X >= 0)
{
if (has[X][0] == true)
{
return true;
}
else
{
return false;
}
}
// if X is negative take the
// absolute value of X.
X = Math.abs(X);
if (has[X][1] == true)
{
return true;
}
return false;
}
function insert(a,n)
{
for (let i = 0; i < n; i++)
{
if (a[i] >= 0)
{
has[a[i]][0] = true;
}
else
{
int abs_i = Math.abs(a[i]);
has[abs_i][1] = true;
}
}
}
// Driver code
let a=[-1, 9, -5, -8, -5, -2];
let n = a.length;
insert(a, n);
let X = -5;
if (search(X) == true)
{
document.write("Present");
}
else
{
document.write("Not Present");
}
// This code is contributed by rag2127
</script>
Producción
Present
Este artículo es una contribución de ShivamKD . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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