时间戳

首页 > 解决方案 > 改进 Python 中的 HashSet 设计

python - 改进 Python 中的 HashSet 设计

问题描述

在这里学习！

我已经设法将这个解决方案汇集到一个关于 Leetcode 的问题中！以下是此解决方案的统计数据：运行时间：1236 毫秒，比 Python3 在线提交的 Design HashSet 内存使用量快 17.28%：18.7 MB，少于 Python3 在线提交的 Design HashSet 的 83.53%。

现在 - 我希望 Leetcode 能够展示一个理想或最佳实践的解决方案，这样我就可以与我的比较和学习！但他们没有！

所以，如果你们中的任何人可以在这里，将不胜感激！（批评并展示您的最佳实践解决方案）

任务描述

我的解决方案

class MyHashSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.TheSet = []
        

    def add(self, key: int) -> None:
        if self.contains(key):
            pass
        else:
            if key >= 0 and key <= 10**6:
                self.TheSet.append(key)
            else:
                pass

    def remove(self, key: int) -> None:
        if self.contains(key):
            self.TheSet.remove(key)
        else:
            pass

    def contains(self, key: int) -> bool:
        if key in self.TheSet:
            return True
        else:
            return False
        


# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)```

标签： pythonhashset

解决方案

我找到了挑战并玩了一点。我想问题是你没有使用 HashSet 的基本概念，这将在你在 LeetCode 上尝试的挑战中解释。这也是一个问题，他们解释了 HashMap 的作用。会检查出来！

我还根据this answer为您制定了解决方案。它的运行时间优于 80%，内存使用率优于 90%。显然，这可以进一步改进，但我认为它包含了基本概念。

class MyHashSet:

    def __init__(self):
        self.contents = [None] * 1_000
        
    def hash(self, x):
        return x % (2 ** 61 - 1)
    
    def add(self, key:int) -> None:
        key_hash = self.hash(key) % 1_000
        bucket = self.contents[key_hash]
        
        if bucket is None:
            self.contents[key_hash] = [key]
        elif key not in bucket:
            bucket.append(key)
        return None

    def remove(self, key: int) -> None:
        key_hash = self.hash(key) % 1_000
        bucket = self.contents[key_hash]
        
        if bucket is not None:
            if key in bucket:
                bucket.remove(key)
        else:
            pass
        
    def contains(self, key: int) -> bool:
        key_hash = self.hash(key) % 1_000
        bucket = self.contents[key_hash]
        
        if bucket is not None:
            if key in bucket:
                return True
            else:
                return False
        else:
            return False

推荐阅读