英文:
Linear probing in Hashing implementation
问题
以下是翻译好的内容:
static int[] linearProbing(int hash_size, int arr[], int N) {
int[] a = new int[hash_size];
for(int i = 0; i < hash_size; i++)
a[i] = -1;
for(int i = 0; i < N; i++) {
int probe = arr[i] % hash_size;
int offset = 1;
while(a[probe] != -1) {
probe = (probe + offset) % hash_size;
}
a[probe] = arr[i];
}
return a;
}
驱动代码可在以下链接中找到:https://i.stack.imgur.com/ULVdd.png
英文:
I am trying to solve this problem where I need to implement Linear Probing.
Given an array of integers and a hash table size. Fill the array elements into a hash table using Linear Probing to handle collisions.
Example 1:
Input:
hashSize = 10
sizeOfArray = 4
Array[] = {4,14,24,44}
Output:
-1 -1 -1 -1 4 14 24 44 -1 -1
Example 2:
Input:
hashSize = 10
sizeOfArray = 4
Array[] = {9,99,999,9999}
Output:
99 999 9999 -1 -1 -1 -1 -1 -1 9
Your Task:<br/>
You don't need to read input or print anything.
Your task is to complete the function linearProbing() which takes as input a empty hash table (hash), the hash table size (hashSize), an integers array arr[] and its size N and inserts all the elements of the array arr[] into the given hash table.
The empty cells of the hash table are to be given a value of -1. Also, if there's no more space to insert a new element, just drop that element.
Expected Time Complexity: O(N). <br>
Expected Auxiliary Space: O(1).
Constraints:
1 <= hashSize <= 100
1 <= sizeOfArray <= 100
0 <= Array[] <= 105
The code I wrote is:
static int[] linearProbing(int hash_size, int arr[], int N) {
int[] a = new int[hash_size];
for(int i = 0; i < hash_size; i++)
a[i] = -1;
for(int i = 0; i < N; i++) {
int probe = arr[i] % hash_size;
int offset = 1;
while(a[probe] != -1) {
probe = (probe + offset) % hash_size;
}
a[probe] = arr[i];
}
return a;
}
The given testcases are running. But when submitting I am getting TLE. Please help.
The driver code is given as follows =
https://i.stack.imgur.com/ULVdd.png
答案1
得分: 1
你漏掉了一个关键点,当数组大小大于哈希表时,只需跳过剩余部分。
这也可能是一个简单的要点,只需用哈希表大小替换N并进行迭代。这将使您只需在arr
包含元素的情况下进行迭代。
static int[] linearProbing(int hash_size, int arr[], int N) {
// 这是您的代码中缺失的部分
int iterating_size = N > hash_size ? hash_size : N;
int[] a = new int[hash_size];
for (int i = 0; i < hash_size; i++)
a[i] = -1;
int started = -1;
for (int i = 0; i < iterating_size; i++) {
int probe = arr[i] % hash_size;
int offset = 1;
while (a[probe] != -1) {
probe = (probe + offset) % hash_size;
}
a[probe] = arr[i];
}
return a;
}
英文:
You missed out one single point, when the array size is bigger than the hash table, just skip the rest.
This could also be the simple point, Just replace N with hash_size and iterate. This would let you only iterate as long as arr
contains elements
static int[] linearProbing(int hash_size, int arr[], int N) {
//This is what was missing from your code
int iterating_size = N>hash_size? hash_size : N;
int[] a = new int[hash_size];
for(int i = 0; i < hash_size; i++)
a[i] = -1;
int started = -1;
for(int i = 0; i < iterating_size ; i++) {
int probe = arr[i] % hash_size;
int offset = 1;
while(a[probe] != -1) {
probe = (probe + offset) % hash_size;
}
a[probe] = arr[i];
}
return a;
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论