查找一个数组是否是另一个数组哈希表方式(Python)的子集

Question

我想查找一个数组是否是另一个数组的子集，我能想到的方法之一是使用Hashtable，但我想用python实现它。线程中附加的是 c++ 实现。我不是在这里寻找内置函数，例如 set 等。

Python在哈希表方面只有字典的概念，但不确定如何从这里开始。任何建议都会帮助我解决它。

以下是几个列表：

arr1[] = [11， 1， 13， 21， 3， 7]

arr2[] = [11， 3， 7， 1]

方法(c++ 使用哈希(

1( 为 arr1[] 的所有元素创建一个哈希表。

2( 遍历 arr2[]

并在哈希表中搜索 arr2[] 的每个元素。如果未找到元素，则返回 0。

3( 如果找到所有元素，则返回 1。

列表也可以是数百万个数字，因此期望一个可扩展且有效的解决方案。

Answer 1

在 Python 中，你可以为此使用set对象：

>>> arr1 =  [11, 1, 13, 21, 3, 7]
>>> arr2 = [11, 3, 7, 1]
>>> set(arr1).issuperset(arr2)
True

或者更有效地使用：

>>> set(arr2).issubset(arr1)
True

如果您预计 arr2 要小得多...

一些快速计时，似乎它们在 rumtime 中大致相同，尽管从 arr1 创建set需要更多的辅助内存：

>>> import numpy as np
>>> arr1 = np.random.randint(0, 100, (1000000,)).tolist()
>>> len(arr1)
1000000
>>> from timeit import timeit
>>> arr2 = [11, 3, 7, 1]
>>> timeit('set(arr1).issuperset(arr2)', 'from __main__ import arr1, arr2', number=1000)
14.337173405918293
>>> timeit('set(arr2).issubset(arr1)', 'from __main__ import arr1, arr2', number=1000)
14.459818648989312

Answer 2

我想

你想要set例如 set(arr2).issubset(arr1)

Answer 3

试试这个：

i = 0
allIn = True
while i <= len(arr2) and allIn:
    if arr2[i] not in arr1:
        allIn = False
    i += 1

allIn会说第二个列表是否在第一个列表中。

注意：使用set()的另一种解决方案同样有效。

编辑(回应评论(：

我没有使用 for 循环，

因为我不知道如何在allIn False后阻止循环运行(我不知道使用 break 是否有效，所以我保持安全(。

我没有使用set()，因为 OP 明确表示他们不想使用内置函数。我已经发布了我的答案作为已经提供的答案的替代解决方案(但也赞扬了这些答案，因为我相信它们更好(。