擅长:python、mysql、java
<p>根本的问题是您没有为作业使用适当的数据结构。
在这种情况下,使用元组表示集合可能是<em>ok</em>对于<em>small</em>集合,
但是对于<em>大型</em>集合,您可以期望搜索平均值
列表中每个元素的集合总大小的一半
这实际上是其中一组。
对于列表中<em>不是</em>的每个元素,
我们必须搜索<em>两个</em>集合的<em>所有</em>元素来确定这一点。你知道吗</p>
<p>所以任何基于这些数据结构的算法
(即,用元组表示集合)
充其量是<code>O(m*n)</code>,其中<code>m</code>是列表的大小
<code>n</code>是集合的大小。你知道吗</p>
<p>我们真的没有办法减少<code>m</code>组件
-我们必须检查列表中的每一个元素以确定哪一组
(如果有的话)它属于。你知道吗</p>
<p>但是,我们可以减少<code>n</code>分量。
怎样?通过对我们的集合使用更有效的数据结构。你知道吗</p>
<p>幸运的是,这并不难,因为Python包含一个内置的<code>set</code>类型。
所以第一步是构造两个集合:</p>
<pre><code>a = set((1, 3))
b = set((2, 5))
</code></pre>
<p>现在,我们可以轻松(有效地)确定元素<code>e</code>是否在其中一个集合中:</p>
<pre><code>e = 1
e in a # => True
e in b # => False
</code></pre>
<p>现在,我们只需要循环输入列表并累积结果:</p>
<pre><code>l = [1, 1, 3, 2, 5, 7, 8, 3, 2, 1]
result = 0 # accumulator for result
for e in l:
if e in a:
result += 1
elif e in b:
result -= 1
print result # prints "2"
</code></pre>