哈希实现中的线性探测

Question

我试图解决这个问题，我需要实现线性探测。

给定一个整数数组和一个哈希表大小。使用线性探测将数组元素填充到哈希表中以处理冲突。

例1：

Input:
hashSize = 10
sizeOfArray = 4
Array[] = {4,14,24,44}

Output:
-1 -1 -1 -1 4 14 24 44 -1 -1

例2：

Input:
hashSize = 10
sizeOfArray = 4
Array[] = {9,99,999,9999}

Output:
99 999 9999 -1 -1 -1 -1 -1 -1 9

您的任务：
您不需要读取输入或打印任何内容。

您的任务是完成函数linearProbing（），该函数将空哈希表（hash）、哈希表大小（hashSize）、整数数组arr[]及其大小N作为输入，并将数组arr[]的所有元素插入给定的哈希表中。

哈希表的空单元格将被赋予-1的值。此外，如果没有更多的空间来插入新元素，只需删除该元素。

期望时间复杂度：O（N）。
期望辅助空间：O（1）。

制约因素：

1 <= hashSize <= 100
1 <= sizeOfArray <= 100
0 <= Array[] <= 105

我写的代码是：

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;
}

给定的html" target="_blank">测试用例正在运行。但是当我提交的时候，我得到的是一份工作。请帮忙。

驱动程序代码如下所示=https://i.stack.imgur.com/ULVdd.png

Answer 1

你漏掉了一个点，当数组大小大于哈希表时，只需跳过其余的。

这也可能是一个简单的问题，只需将N替换为hash_size并迭代即可。只要arr包含元素，就可以进行迭代

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;
}