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.

這是一個搜索問題，可以使用蠻力方法解決。 但是在這里，我們將看到使用哈希表以較低的時間復(fù)雜度解決此類搜索問題。

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 using STL in C++.

哈希表是一種簡單有效的數(shù)據(jù)結(jié)構(gòu)，可以解決O(1)時間復(fù)雜度的搜索問題。 哈希表可以使用C ++中的STL輕松構(gòu)建。

The algorithm to solve the problem:

解決問題的算法：

Create hash table.

創(chuàng)建哈希表 。

Set element pointer to 0. (starting from array[0], first element)

將元素指針設(shè)置為0。(從array [0]，第一個元素開始)

Search for the element in the Hash table.

在哈希表中搜索元素。

If found there is duplicate. Print "duplicate found" & return from program.

如果發(fā)現(xiàn)重復(fù)。 打印“發(fā)現(xiàn)重復(fù)”并從程序返回。

Else insert the element to the hash table.

否則將元素插入哈希表。

If end of the array is reached, exit and print "no duplicate found".

如果到達數(shù)組末尾，請退出并打印“找不到重復(fù)項” 。

Else increase the element pointer and go to step 3 (continue).

否則，增加元素指針，然后轉(zhuǎn)到步驟3(繼續(xù))。

Time complexity: O(1) for searching hash table, O(n) overall

時間復(fù)雜度： O(1)用于搜索哈希表，總體為O(n)

Space complexity: O(n) (for creating hash table)

空間復(fù)雜度： O(n)(用于創(chuàng)建哈希表)

Creating hash table using STL

使用STL創(chuàng)建哈希表

Hash table is created using unordered_set in STL.

哈希表是使用STL中的unordered_set創(chuàng)建的。

C ++實現(xiàn) (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 array 5 enter elements 1 2 3 4 5 No duplicates found........Second run: how many elements do you want in your array 6 enter elements 3 2 1 3 5 6 Duplicate found.....

翻譯自: https://www.includehelp.com/algorithms/given-an-array-of-n-numbers-check-whether-there-is-any-duplicate-or-not.aspx

總結(jié)

以上是生活随笔為你收集整理的给定一个由n个数字组成的数组，请检查是否存在重复项的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。