1. 枚举算法简介
枚举算法(Enumeration Algorithm):也称为穷举算法,指的是按照问题本身的性质,一一列举出该问题所有可能的解,并在逐一列举的过程中,将它们逐一与目标状态进行比较以得出满足问题要求的解。在列举的过程中,既不能遗漏也不能重复。
枚举算法的核心思想是:通过列举问题的所有状态,将它们逐一与目标状态进行比较,从而得到满足条件的解。
由于枚举算法要通过列举问题的所有状态来得到满足条件的解,因此,在问题规模变大时,其效率一般是比较低的。但是枚举算法也有自己特有的优点:
-
多数情况下容易编程实现,也容易调试。
-
建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明。
所以,枚举算法通常用于求解问题规模比较小的问题,或者作为求解问题的一个子算法出现,通过枚举一些信息并进行保存,而这些消息的有无对主算法效率的高低有着较大影响。
2. 枚举算法的解题思路
2.1 枚举算法的解题思路
枚举算法是设计最简单、最基本的搜索算法。是我们在遇到问题时,最应该优先考虑的算法。
因为其实现足够简单,所以在遇到问题时,我们往往可以先通过枚举算法尝试解决问题,然后在此基础上,再去考虑其他优化方法和解题思路。
采用枚举算法解题的一般思路如下:
-
确定枚举对象、枚举范围和判断条件,并判断条件设立的正确性。
-
一一枚举可能的情况,并验证是否是问题的解。
-
考虑提高枚举算法的效率。
我们可以从下面几个方面考虑提高算法的效率:
-
抓住问题状态的本质,尽可能缩小问题状态空间的大小。
-
加强约束条件,缩小枚举范围。
-
根据某些问题特有的性质,例如对称性等,避免对本质相同的状态重复求解。
2.2 枚举算法的简单应用
下面举个著名的例子:「百钱买百鸡问题」。这个问题是我国古代数学家张丘在「算经」一书中提出的。该问题叙述如下:
百钱买百鸡问题:鸡翁一,值钱五;鸡母一,值钱三;鸡雏三,值钱一;百钱买百鸡,则鸡翁、鸡母、鸡雏各几何?
翻译一下,意思就是:公鸡一只五块钱,母鸡一只三块钱,小鸡三只一块钱。现在我们用 $100$ 块钱买了 $100$ 只鸡,问公鸡、母鸡、小鸡各买了多少只?
下面我们根据算法的一般思路来解决一下这道题。
-
一一确定枚举对象、枚举范围和判断条件,并判断条件设立的正确性。
-
确定枚举对象:枚举对象为公鸡、母鸡、小鸡的只数,那么我们可以用变量 $x$、$y$、$z$ 分别来代表公鸡、母鸡、小鸡的只数。
-
确定枚举范围:因为总共买了 $100$ 只鸡,所以 $0 \le x, y, z \le 100$,则 $x$、$y$、$z$ 的枚举范围为 $[0, 100]$。
-
确定判断条件:根据题意,我们可以列出两个方程式:$5 \times x + 3 \times y + \frac{z}{3} = 100$,$x + y + z = 100$。在枚举 $x$、$y$、$z$ 的过程中,我们可以根据这两个方程式来判断是否当前状态是否满足题意。
-
-
一一枚举可能的情况,并验证是否是问题的解。
-
根据枚举对象、枚举范围和判断条件,我们可以顺利写出对应的代码。
-
class Solution:
def buyChicken(self):
for x in range(101):
for y in range(101):
for z in range(101):
if z % 3 == 0 and 5 * x + 3 * y + z // 3 == 100 and x + y + z == 100:
print("公鸡 %s 只,母鸡 %s 只,小鸡 %s 只" % (x, y, z))
-
3.一一考虑提高枚举算法的效率。
-
在上面的代码中,我们枚举了 $x$、$y$、$z$,但其实根据方程式 $x + y + z = 100$,得知:$z$ 可以通过 $z = 100 – x – y$ 而得到,这样我们就不用再枚举 $z$ 了。
-
在上面的代码中,对 $x$、$y$ 的枚举范围是 $[0, 100]$,但其实如果所有钱用来买公鸡,最多只能买 $20$ 只,同理,全用来买母鸡,最多只能买 $33$ 只。所以对 $x$ 的枚举范围可改为 $[0, 20]$,$y$ 的枚举范围可改为 $[0, 33]$。
-
class Solution:
def buyChicken(self):
for x in range(21):
for y in range(34):
z = 100 - x - y
if z % 3 == 0 and 5 * x + 3 * y + z // 3 == 100:
print("公鸡 %s 只,母鸡 %s 只,小鸡 %s 只" % (x, y, z))
3. 枚举算法的应用
3.1 两数之和
3.1.1 题目链接
-
1. 两数之和 – 力扣(LeetCode)
3.1.2 题目大意
描述:给定一个整数数组 nums
和一个整数目标值 target
。
要求:在该数组中找出和为 target
的两个整数,并输出这两个整数的下标。可以按任意顺序返回答案。
说明:
-
$2 \le nums.length \le 10^4$。
-
$-10^9 \le nums[i] \le 10^9$。
-
$-10^9 \le target \le 10^9$。
-
只会存在一个有效答案。
示例:
-
示例 1:
输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
-
示例 2:
输入:nums = [3,2,4], target = 6 输出:[1,2]
3.1.3 解题思路
这里说下枚举算法的解题思路。
思路 1:枚举算法
-
使用两重循环枚举数组中每一个数
nums[i]
、nums[j]
,判断所有的nums[i] + nums[j]
是否等于target
。 -
如果出现
nums[i] + nums[j] == target
,则说明数组中存在和为target
的两个整数,将两个整数的下标i
、j
输出即可。
思路 1:代码
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if i != j and nums[i] + nums[j] == target:
return [i, j]
return []
思路 1:复杂度分析
-
时间复杂度:$O(n^2)$
-
空间复杂度:$O(1)$。
3.2 计数质数
3.2.1 题目链接
-
204. 计数质数 – 力扣(LeetCode)
3.2.2 题目大意
描述:给定 一个非负整数 $n$。
要求:统计小于 $n$ 的质数数量。
说明:
-
$0 \le n \le 5 * 10^6$。
示例:
-
示例 1:
输入 n = 10 输出 4 解释 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7。
-
示例 2:
输入:n = 1 输出:0
3.2.3 解题思路
这里说下枚举算法的解题思路(注意:提交会超时,只是讲解一下枚举算法的思路)。
思路 1:枚举算法(超时)
对于小于 $n$ 的每一个数 $x$,我们可以枚举区间 $[2, x – 1]$ 上的数是否是 $x$ 的因数,即是否存在能被 $x$ 整数的数。如果存在,则该数 $x$ 不是质数。如果不存在,则该数 $x$ 是质数。
这样我们就可以通过枚举 $[2, n – 1]$ 上的所有数 $x$,并判断 $x$ 是否为质数。
在遍历枚举的同时,我们维护一个用于统计小于 $n$ 的质数数量的变量 cnt
。如果符合要求,则将计数 cnt
加 $1$。最终返回该数目作为答案。
考虑到如果 $i$ 是 $x$ 的因数,则 $\frac{x}{i}$ 也必然是 $x$ 的因数,则我们只需要检验这两个因数中的较小数即可。而较小数一定会落在 $[2, \sqrt x]$ 上。因此我们在检验 $x$ 是否为质数时,只需要枚举 $[2, \sqrt x]$ 中的所有数即可。
利用枚举算法单次检查单个数的时间复杂度为 $O(\sqrt{n})$,检查 $n$ 个数的整体时间复杂度为 $O(n \sqrt{n})$。
思路 1:代码
class Solution:
def isPrime(self, x):
for i in range(2, int(pow(x, 0.5)) + 1):
if x % i == 0:
return False
return True
def countPrimes(self, n: int) -> int:
cnt = 0
for x in range(2, n):
if self.isPrime(x):
cnt += 1
return cnt
思路 1:复杂度分析
-
时间复杂度:$O(n \times \sqrt{n})$。
-
空间复杂度:$O(1)$。
3.3 统计平方和三元组的数目
3.3.1 题目链接
-
1925. 统计平方和三元组的数目 – 力扣(LeetCode)
3.3.2 题目大意
描述:给你一个整数 $n$。
要求:请你返回满足 $1 \le a, b, c \le n$ 的平方和三元组的数目。
说明:
-
平方和三元组:指的是满足 $a^2 + b^2 = c^2$ 的整数三元组 $(a, b, c)$。
-
$1 \le n \le 250$。
示例:
-
示例 1:
输入 n = 5 输出 2 解释 平方和三元组为 (3,4,5) 和 (4,3,5)。
-
示例 2:
输入:n = 10 输出:4 解释:平方和三元组为 (3,4,5),(4,3,5),(6,8,10) 和 (8,6,10)。
3.3.3 解题思路
思路 1:枚举算法
我们可以在 $[1, n]$ 区间中枚举整数三元组 $(a, b, c)$ 中的 $a$ 和 $b$。然后判断 $a^2 + b^2$ 是否小于等于 $n$,并且是完全平方数。
在遍历枚举的同时,我们维护一个用于统计平方和三元组数目的变量 cnt
。如果符合要求,则将计数 cnt
加 $1$。最终,我们返回该数目作为答案。
利用枚举算法统计平方和三元组数目的时间复杂度为 $O(n^2)$。
-
注意:在计算中,为了防止浮点数造成的误差,并且两个相邻的完全平方正数之间的距离一定大于 $1$,所以我们可以用 $\sqrt{a^2 + b^2 + 1}$ 来代替 $\sqrt{a^2 + b^2}$。
思路 1:代码
class Solution:
def countTriples(self, n: int) -> int:
cnt = 0
for a in range(1, n + 1):
for b in range(1, n + 1):
c = int(sqrt(a * a + b * b + 1))
if c <= n and a * a + b * b == c * c:
cnt += 1
return cnt
思路 1:复杂度分析
-
时间复杂度:$O(n^2)$。
-
空间复杂度:$O(1)$。
今天的文章数据结构时间复杂度例题详解_数据结构时间复杂度例题详解「建议收藏」分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/81475.html