17968: 整型关键字的散列映射

http://cs101.openjudge.cn/practice/17968/

给定一系列整型关键字和素数P，用除留余数法定义的散列函数H（key)=key%M，将关键字映射到长度为M的散列表中，用线性探查法解决冲突

输入

输入第一行首先给出两个正整数N（N<=1000）和M（>=N的最小素数），分别为待插入的关键字总数以及散列表的长度。 第二行给出N个整型的关键字。数字之间以空格分隔。

输出

在一行内输出每个整型关键字的在散列表中的位置。数字间以空格分隔。

样例输入

4 5
24 13 66 77

样例输出

4 3 1 2

这个题目的输入数据可能不是标准形式，特殊处理，整体读入 sys.stdin.read

def insert_hash_table(keys, M):
    table = [0.5] * M  # 用 0.5 表示空位
    result = []

    for key in keys:
        index = key % M
        i = index

        while True:
            if table[i] == 0.5 or table[i] == key:
                result.append(i)
                table[i] = key
                break
            i = (i + 1) % M

    return result

# 使用标准输入读取数据
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
M = int(data[1])
keys = list(map(int, data[2:2 + N]))

positions = insert_hash_table(keys, M)
print(*positions)