已知存在集合A包含n个整数,从1到n。 存在m个整数a[1..m]。 在集合A中去除这m个整数的的倍数。 编写js函数输出集合中包含的元素的个数。 输入描述: 第一行输入n,m。(1 <= n <= 1e9, 1 <= m <= 10) 第二行输入m个32位整数。 输出描述: 输出集合中包含元素的个数。 输入样例: 5 2 2 3 输出样例: 2
时间: 2023-05-26 19:02:52 浏览: 43
解题思路:
将所有要去除的数的倍数标记出来,剩下的数即为集合中包含的元素。可以使用一个长度为n的布尔数组来表示每个位置上的数是否被标记,初始化为false,从小到大遍历每个数,对于每个未被标记的数p,将p的倍数标记为true,最后遍历布尔数组统计未被标记的数的数量即可。
具体实现中,可以考虑对于第i个去除的数,从i*i开始将i的倍数标记为true,因为小于i的i的倍数已经被标记了。此外,可以在遍历时只从1到sqrt(n)进行,因为大于sqrt(n)的i的倍数一定小于n,并且已经被标记了。注意在标记时需要判断是否超出了n的范围。
时间复杂度为O(nloglogn),空间复杂度为O(n)。
参考代码:
相关问题
已知存在集合A包含n个整数,从1到n。 存在m个整数a[1..m]。 在集合A中去除这m个整数的的倍数。 输出集合中包含的元素的个数。 输入描述: 第一行输入n,m。(1 <= n <= 1e9, 1 <= m <= 10) 第二行输入m个32位整数。 输出描述: 输出集合中包含元素的个数。 输入样例: 5 2 2 3 输出样例: 2
思路:容斥原理。根据题意,需要求出1到n中的数中不被m个给定数整除的数的个数。不妨设S1为1到n中所有数的集合,S2为所有m个给定数的集合,S3为1到n中所有被其中任意一个给定数整除的数所构成的集合,则题目所求的结果即为S1与S3的差集的大小,即$n-|S3-S1|$。由容斥原理,有$|S3-S1|=\sum_{i=1}^{m}(-1)^{i-1}\sum_{1\leq j_1<j_2<\cdots<j_i\leq m}|S_{j_1,j_2,\cdots,j_i}|$,其中$|S_{j_1,j_2,\cdots,j_i}|$表示1到n中所有被第$j_1,j_2,\cdots,j_i$个给定数整除的数所构成的集合。由此可以得到下列代码。具体实现中,可以利用set来实现集合的差集运算。时间复杂度为O(2^mlogn)。当m很小时,可以通过本题;否则需要使用更高效的算法。
已知一个含有n个整数序列a,请设计一个算法找到a中第k(0<k<=n)小的元素
可以使用快速选择算法来找到序列a中第k小的元素。
具体实现步骤如下:
1. 选择序列a中的一个元素x作为主元(pivot)。
2. 将序列a中的元素分成三个部分:小于x的元素集合A,等于x的元素集合B,大于x的元素集合C。
3. 如果A中元素的个数大于等于k,则在A中递归查找第k小的元素;否则,如果A和B中元素的个数之和大于等于k,则x是第k小的元素;否则,在C中递归查找第k-(|A|+|B|)小的元素。
4. 重复执行上述步骤,直到找到第k小的元素。
需要注意的是,快速选择算法的时间复杂度为O(n),最坏的情况下为O(n^2),因此在实际应用中需要考虑序列的特点,避免出现最坏情况的发生。
另外,如果需要找到第k大的元素,可以将序列a中的元素按照从大到小的顺序排序,然后找到第k个元素即可。