3143.正方形中的最多点数

链接：3143.正方形中的最多点数
难度：Medium
标签：数组、哈希表、字符串、二分查找、排序
简介：请你返回 合法 正方形中可以包含的 最多 点数。

题解 1 - python

• 编辑时间：2024-08-03
• 执行用时：154ms
• 内存消耗：47.63MB
• 编程语言：python
• 解法介绍：排序后遍历。

class Solution:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
        get_edge = lambda i: max(abs(points[i][0]), abs(points[i][1]))
        idxs = sorted([i for i in range(len(points))], key = get_edge)
        used = set()
        res = i = 0
        while i < len(idxs):
            edge = get_edge(idxs[i])
            cnt = 1
            if s[idxs[i]] in used: break
            used.add(s[idxs[i]])
            while i + 1 < len(idxs) and get_edge(idxs[i + 1]) == edge:
                i += 1
                if s[idxs[i]] in used: return res
                used.add(s[idxs[i]])
                cnt += 1
            res += cnt
            i += 1
        return res