perl 哈希數(shù)組的哈希

Prerequisite: Hashing data structure

先決條件： 哈希數(shù)據(jù)結(jié)構(gòu)

Problem statement:

問(wèn)題陳述：

Find the first element occurring K times in the array.

查找數(shù)組中出現(xiàn)K次的第一個(gè)元素。

Example:

例：

Input array= [2, 3, 2, 3, 2, 3] K=3 The first element occurring k times is 2. Though both 2 and 3 have occurred 3 times since 2 came first, so the answer would be 2Input array= [1 2 3 1 2] K=3 None of the elements has occurrences 3, so the answer would be -1.

Solution:

解：

We can solve this problem using a hash map (hash table). One thing is clear that to find out the first element occurring k times we need to keep track of frequencies for each unique key.

我們可以使用哈希映射(哈希表)解決此問(wèn)題。 很明顯，要找出出現(xiàn)k次的第一個(gè)元素，我們需要跟蹤每個(gè)唯一鍵的頻率。

So how can we design the problem with the hash table and what will be the hash function?

那么我們?nèi)绾卧O(shè)計(jì)哈希表的問(wèn)題以及哈希函數(shù)是什么呢？

Okay, so here each element is our key and the hash table is has the size of the range of the array. So, if the range of the array is [0,99] then the hash table size would be 100.
What will be our hash function and how would we map the keys to the corresponding location in the hash table?

好的，所以這里的每個(gè)元素都是我們的鍵，哈希表具有數(shù)組范圍的大小。 因此，如果數(shù)組的范圍為[0,99]，則哈希表大小將為100。
我們的哈希函數(shù)將是什么？如何將鍵映射到哈希表中的對(duì)應(yīng)位置？

The hash function h(x)=x here but instead of storing the key itself using linear probing, we will keep the frequency only as we only require that.

這里的哈希函數(shù)h(x)= x ，而不是僅使用線性探測(cè)來(lái)存儲(chǔ)密鑰本身，我們將僅保留頻率，因?yàn)槲覀冎恍枰l率。

So, for example, if we have three 2s as our key, the hash table will store the count (frequency) at location 2.

因此，例如，如果我們有三個(gè)2作為密鑰，則哈希表將在位置2存儲(chǔ)計(jì)數(shù)(頻率)。

So, after the hash table is created,

因此，在創(chuàng)建哈希表之后，

We can check the frequency for each element starting from left to right, one by one. The one satisfying the constraint, i.e., having frequency k will be our answer. In this way, we will get the first element occurring k times. And if none of the elements satisfies then the answer would be -1.

我們可以從左到右逐一檢查每個(gè)元素的頻率。 滿足約束，即具有頻率k的那個(gè)將是我們的答案。 這樣，我們將獲得第一個(gè)出現(xiàn)k次的元素。 如果所有元素都不滿足，則答案將為-1。

So the algorithm will be,

因此算法將是

Step 1:

第1步：

Create the hash table like below: Initially hash table is emptyFor each key in input array: Hash[key]++

Step 2:

第2步：

For each element e:if(hash[e]==k)return e; End for

Dry run with the example:

空運(yùn)行示例：

Input array is = [2, 3, 2, 3, 2, 3] K=3After creating the hash table as step1 we will have Index Value 2 3 3 3Now step2 While scanning for first element having frequency K 2 has frequency 3 and thus we return 3 immediately.For example 2: Input array= [1 2 3 1 2] K=3After creating the hash table as step1 we will have Index Value 1 2 2 2 3 1So after scanning we find that none of the elements has frequency 3, thus answer will be -1.

C++ implementation:

C ++實(shí)現(xiàn)：

// C++ program to find first element // occurring k times in the array #include <bits/stdc++.h> using namespace std;int first_element(vector<int> arr, int n, int k) {//create a hash table where for each key //the hash function is h(x)=x//we will use stl map as hash table and //will keep frequencies stored//so say two keys are mapping to the same location, //then the location will have value 2//instead of the keys itselfmap<int, int> hash;//for each numberfor (auto i : arr) { hash[i]++;}//now for any number if we find //it has frequency k, we simply returnfor (auto i : arr) {if (hash[i] == k)return i;}//otherwise return -1return -1; }int main() {int n, k;cout << "Enter number of elements\n";cin >> n;cout << "Enter k\n";cin >> k;vector<int> arr(n, 0);cout << "Input the array elements\n";for (int i = 0; i < n; i++) {cin >> arr[i];}cout << "Minimum number of operations required to make all elements same is: ";cout << first_element(arr, n, k) << endl;return 0; }

Output:

輸出：

RUN 1: Enter number of elements 6 Enter k 3 Input the array elements 2 3 2 3 2 3 Minimum number of operations required to make all elements same is: 2RUN 2: Enter number of elements 5 Enter k 3 Input the array elements 1 2 3 1 2 Minimum number of operations required to make all elements same is: -1

翻譯自: https://www.includehelp.com/data-structure-tutorial/first-element-occurring-k-times-in-the-array-using-hashing.aspx

perl 哈希數(shù)組的哈希

總結(jié)

以上是生活随笔為你收集整理的perl 哈希数组的哈希_第一个元素使用哈希在数组中出现K次的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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