This is a searching problem which can be solved using brute force approach. But here we are going to see use of hash table to solve such searching problems at lower time complexity.
这是一个搜索问题，可以使用蛮力方法解决。 但是在这里，我们将看到使用哈希表以较低的时间复杂度解决此类搜索问题。
Algorithm:
算法：
Hash table is a simple and effective data structure to solve searching problems in O(1) time complexity. Hash tables can be easily built usingSTL in C++.
哈希表是一种简单有效的数据结构，可以解决O(1)时间复杂度的搜索问题。 哈希表可以使用C ++中的STL轻松构建。
The algorithm to solve the problem:
解决问题的算法：
Createhash table.
创建哈希表。
Set element pointer to 0. (starting from array[0], first element)
将元素指针设置为0。(从array [0]，第一个元素开始)
Search for the element in the Hash table.
在哈希表中搜索元素。
If found there is duplicate. Print"duplicate found"& return from program.
如果发现重复。 打印“发现重复”并从程序返回。
Else insert the element to the hash table.
否则将元素插入哈希表。
If end of the array is reached, exit and print"no duplicate found".
如果到达数组末尾，请退出并打印“找不到重复项”。
Else increase the element pointer and go to step 3 (continue).
否则，增加元素指针，然后转到步骤3(继续)。
Time complexity:O(1) for searching hash table, O(n) overall
时间复杂度：O(1)用于搜索哈希表，总体为O(n)
Space complexity:O(n) (for creating hash table)
空间复杂度：O(n)(用于创建哈希表)
Creating hash table using STL
使用STL创建哈希表
Hash table is created usingunordered_set in STL.
哈希表是使用STL中的unordered_set创建的。
C ++实现 (C++ implementation )
#include<bits/stdc++.h>using namespace std;void checkDuplicate(unordered_set<int> hash, int* a, int n){for(int i=0;i<n;i++){if(hash.find(a[i])==hash.end()){hash.insert(a[i]);}else{printf("Duplicate found.....\n");return;}}printf("No duplicates found........\n");}int main(){int n,x,count=0;printf("how many elements do you want in your array\n");scanf("%d",&n);printf("enter elements\n");// dynamic array createdint* a=(int*)(malloc(sizeof(int)*n)); // creating hash tableunordered_set <int> hash; for(int i=0;i<n;i++){scanf("%d",&a[i]);}// function to check duplicate exists or notcheckDuplicate(hash,a,n); return 0;}
Output
输出量
First run:how many elements do you want in your array5enter elements1 2 3 4 5No duplicates found........Second run:how many elements do you want in your array6enter elements3 2 1 3 5 6Duplicate found.....
翻译自: /algorithms/given-an-array-of-n-numbers-check-whether-there-is-any-duplicate-or-not.aspx
