语言—Python

list和set运行效率

list和set中进行增加、减少的操作都是比较消耗资源的，所以尽量定长

Leetcode 204，计数小于n的质数有多少个：

用set来写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def countPrimes(self, n: int) -> int:
        data = set(range(2, n))
        primes = set()
        while data:
            t = data.pop()
            primes.add(t)
            if t ** 2 > n:
                break
            for i in range(2, n // t + 1):
                try:
                    data.remove(i * t)
                except:
                    pass
        return len(primes) + len(data)

用list来写：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        l = [1] * n      # l为记录1至n-1是否为质数的列表
        l[0] = l[1] = 0       # 0和1不是质数
        for i in range(2, int(n ** 0.5) + 1):
            if l[i] == 1:           # 若i为质数
                l[2*i:n:i] = [0] * ((n - i - 1) // i)    # i的整数倍都不是质数
        return sum(l)

时间差别很大。后者显著要快。