数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中数组中倍数计数的查询
在这个问题中，我们给定一个 arr[] 和 Q 个查询，每个查询包含一个值 m。我们的任务是创建一个程序来解决 C++ 中数组中倍数计数的查询。
问题描述
为了解决这些查询，我们需要计算所有 m 的倍数。为此，我们将检查可被 m 整除的元素。
让我们举个例子来理解这个问题，
输入:arr[] = {4, 7, 3, 8, 12, 15}
Q = 3 query[] = {2, 3, 5}
输出:3 3 1
解释
查询 1：m = 2，数组中的倍数 = 4、8、12。计数 = 3。
查询 2：m = 3，数组中的倍数 = 3、12、15。计数 = 3。
查询 3：m = 5，数组中的倍数 = 15。计数 = 1。
解决方案方法
一个简单的解决方案是遍历每个查询值的数组并计算数组中可被 m 整除的元素的数量。
示例
#include <iostream>
using namespace std;
int solveQuery(int arr[], int N, int m){
int count = 0;
for(int i = 0; i < N; i++){
if(arr[i]%m == 0)
count++;
}
return count;
}
int main(){
int arr[] = {4, 7, 3, 8, 12, 15};
int N = sizeof(arr)/sizeof(arr[0]);
int Q = 3;
int query[] = {2, 3, 5};
for(int i = 0; i < Q; i++)
cout<<"The count of multiples in array "<<solveQuery(arr, N,query[i])<<endl;
return 0;
}输出
The count of multiples in array 3 The count of multiples in array 3 The count of multiples in array 1
此解决方案为每个查询遍历一次数组，这使得时间复杂度为 O(Q*n)。
一个更好的解决方案是使用埃拉托色尼筛法找到所有倍数
以及给定数组的元素计数。其思想是预先计算数组最大值之前所有元素的倍数计数。然后调用预先计算的数组来查找查询的倍数计数。
示例
#include <bits/stdc++.h>
using namespace std;
int preCalcCount[10001];
void PreCalculateMultiples(int arr[], int N){
int maxVal = *max_element(arr, arr + N);
int count[maxVal + 1];
memset(count, 0, sizeof(count));
memset(preCalcCount, 0, (maxVal + 1) * sizeof(int));
for (int i = 0; i < N; ++i)
++count[arr[i]];
for (int i = 1; i <= maxVal; ++i)
for (int j = i; j <= maxVal; j += i)
preCalcCount[i] += count[j];
}
int main(){
int arr[] = {4, 7, 3, 8, 12, 15};
int N = sizeof(arr)/sizeof(arr[0]);
int Q = 3;
int query[Q] = {2, 3, 5};
PreCalculateMultiples(arr, N);
for(int i = 0; i < Q; i++)
cout<<"The count of multiples in array"<<preCalcCount[query[i]]<<endl;
return 0;
}输出
The count of multiples in array 3 The count of multiples in array 3 The count of multiples in array 1
更新于: 2020年10月9日
289 次查看
广告