允许使用负数的索引映射（或普通散列）-yiteyi-C++库

给定一个有限范围数组包含正数和非正数，即元素在-MAX到+MAX的范围内。我们的任务是搜索数组中是否有某个数字在O（1）时间内出现。由于范围有限，我们可以使用索引映射（或琐碎的散列）。我们在一个大数组中使用值作为索引。因此，我们可以在O（1）时间内搜索和插入元素。

null

hmap

如何处理负数？ 其想法是使用大小为[MAX+1][2]的2D数组 算法：

Assign all the values of the hash matrix as 0.
Traverse the given array:
    If the element ele is non negative assign 
        hash[ele][0] as 1.
    Else take the absolute value of ele and 
         assign hash[ele][1] as 1.

搜索任何元素十、在阵列中。

如果X为非负，则检查散列[X][0]是否为1。如果散列[X][0]为1，则该数字存在，否则不存在。
如果X为负值，则取X的绝对值，然后检查散列[X][1]是否为1。如果散列[X][1]为1，则该数字存在

下面是上述想法的实施。

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>                       

输出：

Present

本文由 希瓦姆德 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章