哈希应用—求同一条直线上的点的数量

注意： 1.本博客仅供参考交流使用，请读者务必自行实践，切勿生搬硬套 2.由于笔者水平有限，若文中有错误或者可以改进之处，欢迎在评论区指出

题目 Description

现在输入N个平面坐标系上点，每个点均是过原点的直线（形如y=kx，k为int型，0<k<100）上的点，现要求判断这组输入的点的坐标之中，最多有几个点是在同一条y=kx直线上。PS:每组测试用例中不同斜率k的个数不超过10，要求使用size不超过10的哈希表来储存k。使用线性探测法解决冲突。

Input 首先输入的是点的数量N,接下来是N行数据，每行都是一个点的坐标。

Output 输出一条经过最多点的直线上的点的数量M(int)。

Sample Input 1

9 1 1 2 2 1 50 4 4 3 6 5 5 2 90 3 99 3 9

Sample Output 1

4 分析 第一次更新 这次所贴代码还没有过OJ系统，始终有一个Wrong Answer，笔者还没有查明具体的原因，但是基本的思路还是确定无误，因此先贴上来方便查验交流所用。 首先声明，这并不是一个好的完整的哈希表，然而笔者向来主张具体的场景应用具体的数据结构和相关的操作集，面对这样一个简单的问题，我们显然不需要一个完善的哈希表。 这里只说下核心思想： 哈希表的主题是一个列表，表里的每个元素为一个长度为2的小列表，分别放Key和Value，初始化时key为None，value为0，这里的Key就是咱们的斜率，value每次被寻到就加个1，用来计数。index用key%size来找，如果位置被占了就直接往后找（线性探测法）。

第二次更新 第一次更新的问题找到了 修改如下 self._table[index][0] = key self._table[index][1] += 1 改为 self._table[index] = [key, self._table[index][1] + 1] 可能有些同学会像我一样一头雾水，这两句看起来不是一样吗 现在让我们看一下他们有什么区别 Coding:

from typing import List, Any class HashTable(object): def __init__(self, size: object = 10) -> object: self.size = size self._table = [[None, 0]] * size def find_key(self, key): index = key % self.size t = 0 while self._table[index][0] is not None and key != self._table[index][0]: index = (index + 1) % self.size return index def append(self, key): index = self.find_key(key) if index is not None: self._table[index] = [key, self._table[index][1] + 1] return True else: return False @property def find_max_value_re_key(self): max_value = 0 # max_value_index = -1 for item in self._table: if item[0] is not None: if item[1] > max_value: max_value = item[1] # max_value_index = item[0] else: continue return max_value n = int(input()) h = HashTable() k = 0 for i in range(n): temp_list = input().split(" ") slope = int(temp_list[1]) // int(temp_list[0]) h.append(slope) print(h.find_max_value_re_key)

或者用字典 当然不符合题目要求 只是单纯解决这个问题，我们可以这么做

n = int(input()) hash_table = {} for i in range(n): temp_list = input().split(" ") slope = int(temp_list[1]) // int(temp_list[0]) if slope in hash_table: hash_table[slope] += 1 else: hash_table[slope] = 1 value = hash_table.values() print(max(value))