面试题：Python高效利用if和循环结构优化算法

Question

给定一个非常大的整数列表（假设数量级为10万以上），列表中的元素值范围在1到1000之间。请利用if语句结合循环结构，设计一个高效的算法，统计每个数字出现的次数，并只返回出现次数大于10次的数字及其出现次数，分析并解释你的算法的时间复杂度和空间复杂度。

Answer 1

def count_and_filter(lst):
    count_dict = {}
    for num in lst:
        if num in count_dict:
            count_dict[num] += 1
        else:
            count_dict[num] = 1
    result = []
    for num, count in count_dict.items():
        if count > 10:
            result.append((num, count))
    return result

时间复杂度分析

1. 第一个循环遍历列表，对每个数字进行计数。这个循环的时间复杂度是 $O(n)$，其中 $n$ 是列表的长度。因为对于列表中的每个元素，我们执行的操作（字典查找和更新）平均时间复杂度为 $O(1)$。
2. 第二个循环遍历字典，筛选出出现次数大于10的数字。字典的大小最大为1000（因为数字范围在1到1000之间），所以这个循环的时间复杂度是 $O(m)$，其中 $m$ 最大为1000，是一个常数。

总体时间复杂度为 $O(n + m)$，由于 $m$ 是常数，所以最终时间复杂度为 $O(n)$，$n$ 是列表的长度。

空间复杂度分析

1. 我们使用了一个字典 count_dict 来存储每个数字的出现次数。字典中最多会有1000个不同的键值对（因为数字范围在1到1000之间），所以字典占用的空间是一个常数，可表示为 $O(m)$，$m$ 最大为1000。
2. 我们还使用了一个列表 result 来存储最终的结果，这个列表的大小取决于出现次数大于10的数字的数量，最大也不会超过1000，所以也是常数级别的空间占用 $O(m)$。

总体空间复杂度为 $O(m)$，$m$ 最大为1000，可视为常数。所以空间复杂度为 $O(1)$。