-->
当前位置:首页 > 题库

PROGRAMMING:Hash of integer keyword by square detection

Luz5年前 (2021-05-10)题库515
The task of this problem is very simple: insert the given sequence of non repeating positive integers into a hash table, and output the position of each input number in the table. The hash function used is $$H (key) = key \% tsize $$, where $$tsize $$is the table length of the hash table. It is required to use the square detection method (only increase but not decrease, that is, $$H (key) + I ^ 2 $$) to solve the conflict.
Note that the table length of the hash table is preferably a prime number. If the input given table length is not a prime, you must redefine the table length as the minimum prime greater than the given table length.
###Input format:
First, the first line gives two positive integers $$Msize $$($$Le 10 ^ 4 $$) and $$n $$($$Le Msize $$), which correspond to the length of the input table and the number of input numbers respectively. Next, the second line gives $$n $$non repeating positive integers separated by spaces.
###Output format:
In a row, the position of each number in the hash table is given in the order of input (subscript starts from 0). If a number cannot be inserted, output '-' at its position. The output should be separated by one space, and there should be no extra space at the beginning and end of the line.
###Input example:
```in
4 4
10 6 4 15
```
###Output example:
```out
0 1 4 -
```







answer:If there is no answer, please comment