力扣第204题“计数质数”

2024-06-15 18:20
文章标签 力扣 计数 质数 204

本文主要是介绍力扣第204题“计数质数”,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在本篇文章中,我们将详细解读力扣第204题“计数质数”。通过学习本篇文章,读者将掌握如何使用埃拉托色尼筛法来解决这一问题,并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释,以便于理解。

问题描述

力扣第204题“计数质数”描述如下:

统计所有小于非负整数 n 的质数的数量。

示例:

输入: n = 10
输出: 4
解释: 小于 10 的质数是 2, 3, 5, 7, 共计 4 个。

示例:

输入: n = 0
输出: 0

示例:

输入: n = 1
输出: 0

解题思路

方法:埃拉托色尼筛法
  1. 初步分析

    • 使用埃拉托色尼筛法是一种高效的算法,用于找出一定范围内所有质数。
    • 通过标记合数,筛选出质数。
  2. 步骤

    • 创建一个布尔数组,长度为 n,初始值为 True,表示所有数都是质数。
    • 将数组索引为 0 和 1 的值设为 False,因为 0 和 1 不是质数。
    • 从 2 开始,如果当前数是质数,则将其所有的倍数标记为合数。
    • 最后统计数组中 True 的数量,即为质数的数量。
代码实现
def countPrimes(n):if n < 2:return 0is_prime = [True] * nis_prime[0] = is_prime[1] = Falsefor i in range(2, int(n ** 0.5) + 1):if is_prime[i]:for j in range(i * i, n, i):is_prime[j] = Falsereturn sum(is_prime)# 测试案例
print(countPrimes(10))  # 输出: 4
print(countPrimes(0))   # 输出: 0
print(countPrimes(1))   # 输出: 0
print(countPrimes(30))  # 输出: 10

复杂度分析

  • 时间复杂度:O(n log log n),埃拉托色尼筛法的时间复杂度为 O(n log log n)。
  • 空间复杂度:O(n),用于存储布尔数组。

模拟面试问答

问题 1:你能描述一下如何解决这个问题的思路吗?

回答:我们可以使用埃拉托色尼筛法来解决这个问题。通过创建一个布尔数组表示所有数都是质数,然后从 2 开始,将所有质数的倍数标记为合数,最后统计数组中为 True 的数量,即为质数的数量。

问题 2:为什么选择使用埃拉托色尼筛法来解决这个问题?

回答:埃拉托色尼筛法是一种高效的算法,用于找出一定范围内所有质数。通过标记合数,可以高效地筛选出质数,相比于其他方法,埃拉托色尼筛法的时间复杂度更低,适用于处理较大范围的质数问题。

问题 3:你的算法的时间复杂度和空间复杂度是多少?

回答:算法的时间复杂度为 O(n log log n),埃拉托色尼筛法的时间复杂度为 O(n log log n)。空间复杂度为 O(n),用于存储布尔数组。

问题 4:在代码中如何处理边界情况?

回答:对于 n 小于 2 的情况,可以直接返回 0,因为没有小于 2 的质数。对于其他情况,通过埃拉托色尼筛法处理。

问题 5:你能解释一下埃拉托色尼筛法的工作原理吗?

回答:埃拉托色尼筛法是一种找出一定范围内所有质数的算法。通过创建一个布尔数组表示所有数都是质数,然后从 2 开始,将所有质数的倍数标记为合数。最终,数组中为 True 的位置对应的数即为质数。

问题 6:在代码中如何确保返回的结果是正确的?

回答:通过创建布尔数组,遍历并标记所有合数,最后统计数组中为 True 的数量,确保返回的结果是正确的。

问题 7:你能举例说明在面试中如何回答优化问题吗?

回答:在面试中,如果面试官问到如何优化算法,我会首先分析当前算法的瓶颈,如时间复杂度和空间复杂度,然后提出优化方案。例如,可以通过优化内存使用和减少不必要的计算来提高性能。解释其原理和优势,最后提供优化后的代码实现。

问题 8:如何验证代码的正确性?

回答:通过运行代码并查看结果,验证返回的质数数量是否正确。可以使用多组测试数据,包括正常情况和边界情况,确保代码在各种情况下都能正确运行。例如,可以在测试数据中包含多个范围的数,确保代码结果正确。

问题 9:你能解释一下解决质数计数问题的重要性吗?

回答:解决质数计数问题在数学和计算机科学中具有重要意义。质数在数论中扮演着重要角色,通过学习和应用埃拉托色尼筛法,可以提高处理质数问题的能力。在实际应用中,质数广泛用于加密算法、数据结构和算法设计等领域。

问题 10:在处理大数据集时,算法的性能如何?

回答:算法的性能取决于范围 n 的大小。在处理大数据集时,通过优化埃拉托色尼筛法的实现,可以显著提高算法的性能。例如,通过减少不必要的计算和优化内存使用,可以减少时间和空间复杂度,从而提高算法的效率。

总结

本文详细解读了力扣第204题“计数质数”,通过使用埃拉托色尼筛法高效地解决了这一问题,并提供了详细的解释和模拟面试问答。希望读者通过本文的学习,能够在力扣刷题的过程中更加得心应手。

这篇关于力扣第204题“计数质数”的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1064219

相关文章

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

YOLOv8/v10+DeepSORT多目标车辆跟踪(车辆检测/跟踪/车辆计数/测速/禁停区域/绘制进出线/绘制禁停区域/车道车辆统计)

01:YOLOv8 + DeepSort 车辆跟踪 该项目利用YOLOv8作为目标检测模型,DeepSort用于多目标跟踪。YOLOv8负责从视频帧中检测出车辆的位置,而DeepSort则负责关联这些检测结果,从而实现车辆的持续跟踪。这种组合使得系统能够在视频流中准确地识别并跟随特定车辆。 02:YOLOv8 + DeepSort 车辆跟踪 + 任意绘制进出线 在此基础上增加了用户

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

力扣接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 示例 2: 输入:height

归并排序/计数排序

1:归并排序 1.1:代码 void _MergeSort(int* arr, int left, int right, int* tmp){if (left >= right){return;}int mid = (left + right) / 2; _MergeSort(arr, left, mid, tmp); _MergeSort(arr, mid+1, righ

牛客小白月赛100(A,B,C,D,E,F三元环计数)

比赛链接 官方讲解 这场比较简单,ABC都很签到,D是个不太裸需要预处理的 B F S BFS BFS 搜索,E是调和级数暴力枚举,F是三元环计数。三元环考的比较少,没见过可能会偏难。 A ACM中的A题 思路: 就是枚举每个边变成原来的两倍,然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2,比如 1 4 8 这组数据,也不能只给第二短边乘 2 2 2,比

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1

【CF】C. Glass Carving(二分 + 树状数组 + 优先队列 + 数组计数)

这题简直蛋疼死。。。。。 A了一下午 #include<cstdio>#include<queue>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 200005;int h,w,n;int C1[maxn],C2[maxn];int